%%%% THIS FILE IS AUTOMATICALLY GENERATED
%%%% DO NOT EDIT THIS FILE DIRECTLY,
%%%% ONLY EDIT THE SOURCE, tom-51/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*{corn}{Corollary to Lemma 1}
\newtheorem{lemma}{Lemma}
\newtheorem*{sub}{Sublemma}
\newtheorem*{thm}{Theorem}
\newtheorem*{prop}{Proposition}
\newtheorem{q}{Problem}
\theoremstyle{definition}
\newtheorem{defn}{Definition}
\newtheorem{fact}{Fact}
\newtheorem*{claim}{Claim}
\newtheorem*{remark}{Remarks}
\newtheorem*{app}{Applications}
\newtheorem*{conj}{Conjecture}
\title{A Density Version of a Geometric Ramsey Theorem}
\author{T. C. Brown and J. P. Buhler}
\date{}
\maketitle
\begin{center}{\small {\bf Citation data:} T.C. Brown and J.P. Buhler, \emph{A density version of a geometric {Ramsey}
theorem}, J. Combin. Theory Ser. A \textbf{25} (1982), 20--34.}\bigskip\end{center}
\begin{abstract}
Let $V$ be an $n$-dimensional affine space over the field with $p^d$ elements, $p \ne 2$. Then for every $\varepsilon > 0$ there is an $n(\varepsilon)$ such that if $n = \dim(V) \geq n(\varepsilon)$ then any subset of $V$ with more than $\varepsilon |V|$ elements must contain 3 collinear points (i.e., 3 points lying in a one-dimensional affine subspace).
\end{abstract}
\section{Introduction} \label{sec: 1}
A celebrated result due to Van der Waerden says that if the integes in the interal $[1,n]$ are colored with $r$ colors then there is a monochromatic arithmetic progression of length $k$ if $n$ is large enough as a function of $k$ and $r$. A stronger result, proved for $k = 3$ by Roth~\cite{roth1954} and arbitrary $k$ by Szmer\'{e}di~\cite{szemeredi1969,szemeredi1975}, asserts that for all $\varepsilon > 0$ there is an $ n = n(\varepsilon, k)$ such that any set of integers $A \subset [1,n]$ with more than $\varepsilon n $ elements must contain an arithmetic progression of length $k$. Alternatively, if $f_k(n)$ denotes the size of the maximal subset of $\{1,\dots,n\}$ that does not contain a $k$-term arithmetic progression then $f_k(n) = o (n)$. This statement implies Van der Waerden's Theorem and could be regarded as a ``density version" of that result.
Let $F$ be a finite field of odd characteristic and let $V$ be an $n$-dimensional vector space over $F$. Three distinct points $x,y,z$ in $V$ are said to be collinear if $z- y$ is a scalar multiple of $y - x$; i.e., $x = u + rv$, $y = u + sv$, $z = u + tv$ for distinct $r,s$, and $t$ in $F$. The goal of this paper is to prove a density version of the following known fact (see~\cite{graham1981} or~\cite{roth1954}): if the points of $V$ are colored with $r$ colors and $n$ is large enough as a function of $r$ then there are 3 collinear points of the same color (in fact there is a whole line, plane, ...; see Section~\ref{sec: 4}). Thus we intend to show that if $\varepsilon > 0$ is given and $A$ is a subset of $V$ with $|A| > \varepsilon |V|$ then $A$ contains 3 collinear points if $n = \dim_F V$ is large enough as a function of $\varepsilon$.
Note that the relation of collinearity depends only on the structure of $V$ as an affine space over $F$ so that we might as well take $V$ to be an $n$-dimensional affine space over $F$ (i.e., a set that is isomorphic to $F^n$ by an isomorphism that is determined only up to an affine transformation of $F^n$).
The method of the proof is based on ideas in Graham's exposition in~\cite{graham1981} of Szmer\'{e}di's proof of Roth's theorem on 3-term arithmetic progressions. The main theorem is proved in the third section of the paper. The second section contains some needed technical results, and the fourth section contains some further remarks and corollaries. Perhaps, as with some other mathematical papers, the easiest approach for the reader is obtained by reading the sections in reverse order.
Our primary interest is in the case in which $F$ is the field with 3 elements. In this special case 3 collinear points form an affine line. Since a combinatorial line is an affine line (but not vice versa) our result could be viewed as a weakening of the density version of the Hales-Jewett Theorem (see Section~\ref{sec: 4}; other geometric Ramsey-type theorems should also have density analogues). It might be worthwhile to point out to the reader that Graham offers a monetary reward~\cite{graham1981} for a proof of the density version of the Hales-Jewett result for three-element sets.
An ovaloid in the projective space $\mathbb{P}^r(F)$ is a subset that is maximal with respect to the property of not containing 3 collinear points~\cite{hill1978,segre1959}; they give certain codes that can correct one error and detect three errors. In Section~\ref{sec: 4} we show how our main result implies that the density of ovaloids must be asymptotically small. Thus if $A$ is an ovaloid then $|A|/|\mathbb{P}^r(F)|$ goes to 0 as $r$ goes to infinity.
\section{Lemmas} \label{sec: 2}
We need two substantial technical side results for the proof of the main theorem. In order not to disrupt the flow of the main argument these results are presented in this section.
The first lemma is an extension of an analogue of an initial lemma in the proof of Roth's Theorem in Ref.~\cite{graham1981}; we incorporate the proof given there.
Let $F$ be a finite field with $q$ elements ($q$ not necessarily odd). If $V$ is an $n$-dimensional vector space over $F$ and $a,x_1,\dots,x_k$ are elements of $V$ then define a set
\[ Q(a,x_1,\dots,x_k) = \{a + \alpha_1x_1 + \cdots + \alpha_kx_k: \alpha_i = 0,1\}. \]
Thus $Q(a,x_1,\dots,x_k)$ is a translate of the 0-1 linear combinations of the $x_i$.
\begin{lemma} \label{lemma: 1}
For all $\varepsilon > 0$ there is a $C$ depending only on $q$ and $\varepsilon$ such that if $A$ is a subset of $V$ that does not contain 3 collinear points and $|A| > \varepsilon |V|$, then there are $a,x_1,\dots,x_k$ in $V$ such that
\begin{align*}
&Q(a,x_1,\dots,x_k) \subset A, \\
&k > \frac{\log\log |V|}{\log (q)} + C = O(\log^2 |V|), \\
&x_1,\dots,x_k \textup{ are linearly independent}. \end{align*}
\end{lemma}
\emph{Remark on notation.} Throughout this paper $|A|$ denotes the size of a set $A$, $\log^m(x)$ denotes the $m$-fold iterated logarithm $\log(\log(\cdots$, and $o(x)$ and $O(x)$ refer to the behavior of functions as $x \to \infty$.
\begin{proof} First we show by induction on $d$ that if $A$ is a subset of $V$ with $|A| \geq t_d$, where $t_d = 4|V|^{1 - 1/2^d}$, then there are $a,x_1,\dots,x_d$ in $V$ with $Q(a,x_1,\dots,x_d)$ contained in $A$. For $d = 1$ the result is trivial. Take $d \geq 2$ and assume the result for $d - 1$. Assume that $A = \{a_1,\dots,a_t\}$ is a subset of $V$ with $|A| = t \geq t_d$. Note that
\[ \binom{t_d}{2} \geq t_d^2/4 = 4|V|^{1 - 2^{-(d -1 )}} \cdot |V| = t_{d - 1} |V|. \]
Hence more than $t_{d - 1}$ of the diffrerences $a_i - a_j$, $i > j$, are equal; say, $\{w\} = \{a_{i_k} - a_{j_k}: 1 \leq k \leq t_{d - 1}\}$. Now let $A' = \{a_{j_k}\}$ and apply the induction hypothesis to $A'$ to get $a,x_1,\dots,x_{d-1}$ in $V$ with $Q(a,x_1,\dots,x_{d-1}) \subset A'$. Because of the definition of $w$ and $A'$ it follows that if $x'$ is in $A'$ then $x' + w$ is in $A$. Thus $Q(a,x_1,\dots,x_{d-1},w) \subset A$, as required.
Now observe that if
\[ d = \frac{\log\log |V| - \log \log (4/\varepsilon)}{\log(2)} \]
then $t_d = \varepsilon |V|$. The above argument then shows that we can find
\[ Q(a,x_1,\dots,x_d) \subset A \]
with $d> \log^2|V|/\log(2) + C$, where $C$ is the generic symbol for a constant that depends on $\varepsilon$ and $q$ but not on $n = \dim_F V$.
Now we make use of the assumption that $A$ contains no 3 collinear points.
\begin{claim} The linear combinations $a + \sum \alpha_i x_i$ in the $Q(a,x_1,\dots)$ constructed above are distinct.
\end{claim}
\begin{proof} If two such combinations are equal, say,
\[ a + \sum \alpha_i x_i = a + \sum \beta_i x_i, \quad \alpha_i,\beta_i \textup{ in } \{0,1\}, \]
then we might as well assume that $\alpha_i \ne \beta_i$ for all $i$. Find $j$ such that $\alpha_j = 1$. Then
\[ x_j + \sum\alpha_i x_i = \sum \beta_i x_i, \]
where the sums now run over all $i \ne j$. Then the three vectors
\begin{align*}
u &= a + \sum \beta_i x_i + x_j, \\
v &= a + \sum \beta_i x_i, \\
w &= a + \sum \alpha_i + x_i \end{align*}
are collinear elements of $A$; indeed by the definition of $x_j$
\[ w - v = \sum \alpha_i x_i - \sum \beta_i x_i = -x_j = v - u. \]
This finishes the proof of the claim.
\end{proof}
Now we use the Claim to extract a linearly independent subset from $x_1,\dots,x_d$ of sufficient size.
We now know that $|Q(a,x_1,\dots,x_d)| = 2^d$. The vectors $x_1,\dots,x_d$ must therefore span a linear subspace of dimension at least $k$, where
\[ q^k \leq 2^d < q^{k + 1}, \]
i.e., $k \simeq (\log(2)/(\log(q))d$. Deleting the dependent $x_i$ and renumbering gives us the desired set $x_1,\dots,x_k$ with
\[ k > \frac{\log^2|V|}{\log(q)} + C. \]
This finishes the proof of Lemma~\ref{lemma: 1}.
\end{proof}
For the next lemma we take $V$ and $F$ as above except that now $F$ must be a prime field with $p$ elements where $p$ is an odd prime. To fix the ideas let $W$ be an $m$-dimensional linear subspace of the $n$-dimensional $F$-vector space $V$ and let $W'$ be a translate of $W$ (one could also let $W'$ be an arbitrary affine space for an $F$-vector space $W$). Choose a basis $x_1,\dots,x_m$ for $W$ and let
\[ P = \{\alpha_1 x_1 + \cdots + \alpha_mx_m: \alpha_i = 0,1\} \]
be the 0-1 linear combinations of the basis elements.
Throughout the following lemma let $f_k(x)$ denote the real-valued function on $[0,1]$ given by
\[ f_k(x) = x + \frac{2}{k - 1} x(x - 1) = \frac{k + 1}{k - 1} x - \frac{2}{k - 1} x^2. \]
\begin{lemma} \label{lemma: 2}
If $A$ is a subset of $W'$ with density $a$ then the density of $A + P$ is at least $f_p(a)$; i.e.,
\[ |A| = a|W'| \quad \textup{implies} \quad |A + P| \geq f_p(a) |W'|. \]
\end{lemma}
\emph{Remarks} The statement is trivially true for the extreme cases $a = 0$ or $a = 1$. The statement is false if $W'$ is an affine space over $F_q$, $q= p^d$, $d > 1$. Indeed, if $A$ is the $\mathbb{F}_p$ span of $P$ in $W' = W$ then $A + P = A$ which contradicts the bound given.
\begin{proof} The proof is by induction on $m$. For $m = 1$ and $a \ne 0,1$, we have
\[ |A + P| \geq |A| + 1 = a|W| + 1 = ap + 1 \geq \left( a + \frac{2}{p -1}a(1 - a) \right) p \]
since $a(1 - a) \leq \frac{1}{4}$, so that
\[ \frac{2p}{p - 1} a (1 - a) \leq \frac{p}{2(p -1)} \leq 1. \]
Now assume that the lemma is true for all spaces of dimensions smaller than $m$. Write
\[ W' = \bigcup W_r, \quad r \textup{ in } F = \mathbb{F}_p, \]
where each $W_r$ is an affine hyperplane and
\[ W_r = W_0 + r\cdot x_m. \]
(If we think of the $x_i$ as the standard basis vectors in $W' = F^m$ then we could take $W_r$ to be the set of vectors whose last coordinate was equal to $r$.)
To simplify the notation let $P'$ be the 0-1 linear combinations of $x_1,\dots,x_{m - 1}$ and let $x = x_m$. Put $A_r = A \cap W_r$. Then elements of $A + P$ are of two kinds; either they are in
\[ A_r + P' \subset W_r \]
for some $r$ in $F$, or they are in
\[ A_r + P' + x \subset W_{r + 1} \]
for some $r$ in $F$. By counting up the elements of $A + P$ that are of the first kind and then including any elements of the second kind left over we can bound $|A + P|$ from below:
\begin{equation} |A + P| \geq \sum |A_r + P'| + \sum \sup(0,|A_r + P'| - |A_{r + 1} + P'|), \label{eq: 1} \end{equation}
where both summations are over all $r$ in $F = \mathbb{F}_p$. To bound the second term we need an easy estimate:
\begin{sub}
If $k \geq 2$ and $y_1,\dots, y_k$ are real numbers then
\[ \sum_{i=1}^k \sup(0,y_{i + 1} - y_i) \geq y_b - y_c \]
for any $b$ and $c$ (where we let $y_{k + 1}$ be another name for $y_1$).
\end{sub}
\begin{proof} Use induction on $k$ together with the fact that
\[ \sup( 0,v - u) + \sup (0, w - v) \geq \sup(0 ,w-u) \]
(which is easy to check by enumerating the possible cases). End of sublemma.
\end{proof}
Now let $a_r = |A_r|/|W_r|$ be the density of $A_r$ in $W_r$. Note that the density $a$ of $A$ in $W'$ is the average of the $a_r$. Apply the sublemma to the second term in~(\ref{eq: 1}) to get
\begin{align*}
|A + P| &\geq \sum_{r \in F} |A_r + P'| + |A_b + P'| - |A_c - P'| \\
&= 2|A_b + P'| + \sum_{r \ne b,c} |A_r + P'|. \end{align*}
Now choose $b$ so that $a_b$ is the largest of the various $a_i$ and choose $c$ so that $a_c$ is the smallest of the $a_i$. Divide by $|W_r| = |W|/p$ and use the inductive assumption to get
\[ p\frac{|A + P|}{|W|} \geq 2f_p(a_b) + \sum_{r \ne b,c} f_p(a_r). \]
Since Lemma~\ref{lemma: 2} just says that $|A+ P|/|W|$ is at least as big as $f_p(a)$ it is clear that the proof of the lemma will be finished if we can demonstrate the following property of the function $f_k(x)$:
\begin{claim}
If $k \geq 3$ and we are given real numbers in $[0,1]$ satisfying
\[ 0 \leq y_1 \leq \cdots \leq y_k \leq 1 \]
then
\[ f_k(y_2) + f_k(y_3) + \cdots + f_k(y_{k - 1}) + 2f_k(y_k) \geq kf_k\left( \frac{y_1 + \cdots + y_k}{k} \right). \]
\end{claim}
\begin{proof}[Proof of the claim]
We work backwards. Write the desired inequality as
\[ f_k(y_k) - f_k(y_1) \geq k\cdot f_k(\bar{y}) - f_k(y_1) - \cdots - f_k(y_k), \]
where $\bar{y}$ denotes the average of the $y_i$. If we plug in the definitoin of
\[ f_k(x) = \frac{k + 1}{k - 1} x - \frac{2}{k - 1} x^2 \]
then all of the linear terms in the $y_i$ on the right hand side cancel. Multiply by $k(k - 1)/2$. The result is
\begin{align*}
\frac{k(k + 1)}{2} (y_k - y_1) - k(y_k^2 - y_1^2) &\geq -(k\bar{y})^2 + ky_1^2 + \cdots + ky_k^2 \\
&= \sum_{i > j} (y_i - y_j)^2. \end{align*}
The left hand side can be rewritten, after doing a little juggling, as
\[ \frac{k(k - 1)}{2}(y_k - y_1)^2 + k(y_k - y_1)\left( \frac{k + 1}{2} - \frac{k + 1}{2}y_k + \frac{k - 3}{2} y_1 \right). \]
The desired inequality is now evident since the second term in the preceding expression is positive and $(y_k - y_1)^2$ is greater than each of the $k(k - 1)/2$ terms of the form $(y_i - y_j)^2$. End of Lemma~\ref{lemma: 2}
\end{proof}
\end{proof}
\section{Theorem} \label{sec: 3}
In this section we prove the following result.
\begin{thm} Let $p$ be an odd prime and $F$ the field with $q = p^d$ elements. For every $\varepsilon > 0$ there is an $N(\varepsilon)$ such that if $V$ is an affine space over $F$ with $|V| \geq N(\varepsilon)$, and $A$ is a subset of $V$ with $|A| \geq \varepsilon |V|$, then $A$ contains 3 collinear points.
\end{thm}
\begin{proof} Put $N = |V| = q^n$ and let $f(N)$ denote the largest possible size of a subset of $V$ that does not contain 3 collinear points. We shall call such a subset ``line-free." The goal is to prove that $f(N) = o(N)$ as $N$ becomes large.
First note that if $V$ is an $F$ vector space then it can be regarded as an $\mathbb{F}_p$ vector space by restriction of scalars. If $\{u,v,w\}$ is a set of collinear points in $V$ regarded as an $\mathbb{F}_p$ vector space then it is certainly a collinear set if $V$ is regarded as an $F$ vector space. Thus any line-free set over $F$ is also a line-free set if $V$ is thought of as an $\mathbb{F}_p$ vector space.
Thus the theorem for arbitrary $q$ follows from the theorem for prime fields so we begin by fixing $q = p = $ an odd prime and considering affine spaces $V$ over $F = \mathbb{F}_p$. At any stage we are free to choose an identification $V \cong F^n$ since the notion of collinearity is independent of the affine space isomorphism that is chosen.
Let
\[ V = \bigcup V_r, \quad r \in F = \mathbb{F}_p \]
be a disjoint union of $n - 1$ dimensional affine subspaces. (For instance, we could take $V_r$ to be the set of elements of $V \cong F^n$ whose $n$th coordinate is equal to $r$.) The intersection of a line-free set in $V$ with each of the $V_r$ is any $n - 1$ dimensional line-free set. Therefore $f(p^n) \leq p \cdot f(p^{n -1}))$ so that the sequence $f(p^n)/p^n$ is decreasing to a limit
\[ \lim_{N \to \infty} \frac{f(N)}{N} = c. \]
The Theorem asserts that $c = 0$.
Assume that $c > 0$. Choose $\varepsilon > 0$ with $\varepsilon < c^2/8p$ and let $N_0(\varepsilon)$ have the property that if $A$ is a maximal line-free set in $V$ and $|V| \geq N_0(\varepsilon)$ then
\begin{equation} (c - \varepsilon )|V| < |A| < (c + \varepsilon) |V|, \label{eq: 2} \end{equation}
Now choose $N$ to be \emph{very very very } large (i.e., the order of $\exp(\exp(\exp(N_0(\varepsilon))))$) and let $A$ be a line-free set in $V$ that is of maximum size where $|V| = N$. The exact conditions that we need on $N$ are that the estimate~(\ref{eq: 2}) should apply to vector spaces with $\log^3N$ elements and that a certain explicit $o(N)$ term that will arise later should be less than $c^2N/4$.
Write $V = \bigcup V_r$ as above and let $A_r = A \cap V_r$. Even though $A_r$ is not necessarily a maximal line-free set inside $V_r$ we can still get a lower bound on its size
\begin{align}
|A_r| = |A| - \sum_{s \ne r} |A_s| &> (c - \varepsilon)N - (p - 1)(c + \varepsilon) \frac{N}{p} \notag \\
&= (c - (2p - 1)\varepsilon)\frac{N}{p}. \label{eq: 3} \end{align}
Note that if $u$ is in $V_0$ and $v$ is in $V_1$ then there is a unique $w$ in $V_r$ such that $u,v,$ and $w$ are collinear (in fact $w = (1 - r)u + rv$). Thus elements in $A_0$ and $A_1$ have the effect of excluding certain elements of $V_r$ from being in $A_r$.
In order to exploit this idea apply Lemma~\ref{lemma: 1} to the subset $A_1$ of $V_1$ (which can be done since the density of $A_1$ in the affine space $V_1$ is at least $c - (2p - 1)\varepsilon > 0$). We get $a$ in $A_1$ and $x_1,\dots,x_k$ such that the $x_i$ are linearly independent, $k = O(\log^2N)$, and
\[ Q(a,x_1,\dots,x_k) = \{a + \alpha_1x_1 + \cdots + \alpha_k x_k : \alpha_i = 0,1\} \subset A_1. \]
Define $Q_0 = \{a\}$ and for $1 \leq i \leq k$ define
\[ Q_i = \{a + \alpha_1 x_i + \cdots + \alpha_i x_i\} \subset Q_k(a,x_1,\dots,x_k). \]
For $r \ne 0,1$ put
\begin{align*} M_{i,r} = \{w \in V_r: &\textup{there is a collinear set $u,v,w$} \\
&\textup{with $u$ in $A_0$ and $v$ in $Q_1$} \}. \end{align*}
Two immediate observations are that
\[ M_{i,r} \cap A_r = \emptyset \]
and that
\begin{equation} |M_{i,r}| \geq |M_{0,r}| = |A_0| > (c - (2p - 1)\varepsilon)\frac{N}{p}. \label{eq: 4} \end{equation}
Also we will need the following easy observation.
\emph{Fact.} If $u_0, u_1$, and $u_r$ are collinear, where $u_i$ is in $V_i$, then $u_0,u_1 + v$, and $u_r + rv$ are collinear.
This implies that
\[ M_{i + 1, r} = M_{i,r} \cup (M_{i,r} + rx_{i + 1}). \]
At this point we fix for the duration of the proof an element $r$ of $F$, $r \ne 0,1$. To simplify the notation put $M_{i,r} = M_i$.
Since we must certainly have $|M_k| \leq N$ the sequence of numbers $|M_{i + 1}\setminus M_i|$ sums to at most $N$ and therefore the ``average" value is less than $N/k \simeq O(N/\log^2N)$. Thus we can find a consecutive run $i + 1, i+2, \dots, i + m$ with
\[ |M_{j + 1} \setminus M_j| < \frac{N}{\log^3N}, \quad i + 1\leq j \leq i + m, \]
for $m$ as large as $k/\log^3 N \simeq O(\log^2N/\log^3N)$.
In fact we merely take such a run with $m$ such that
\[ N_0(\varepsilon) \leq p^m < \log^3 N \]
so that $m = O(\log^4N)$. Fixing $i$ and $m$ as above let
\[ W = \langle x_j: i + 1\leq j \leq i + m \rangle \]
be the linear space spanned by the indicated $x_j$. Let
\[ P = \left\{ \sum_{j =i + 1}^{i + m} \alpha_j x_j : \alpha_j = 0,1\right\} \]
be the 0-1 linear combinations of the given basis of $W$. To simplify the notation even further put $M = M_i$.
By the Fact above together with the definitions
\[ M + rP \subseteq M_{i + m}. \]
Consequently
\begin{equation} |M + rP\setminus M| < m \frac{N}{\log^3N} = O\left( \frac{N\log^4N}{\log^3N} \right) = o(N) \label{eq: 5} \end{equation}
since $M_{i + m} \supset M + rP$ is obtained from $M$ by a sequence of $m$ steps of adding at most $N/\log^3N$ vectors.
Since the coset ($=$translate) $a + W$ of the subspace $W$ is contained in $V_1$ there is a coset of $W$ contained in $V_r$ and hence we can find a decomposition
\[ V_r = \bigcup W_s \]
in which each of the $W_s$ is a coset of the vector space $W$. Each of the $W_s$ has $|W| = p^m$ elements and there are $(N/p) \cdot p^{-m} \simeq O(N/\log^3N)$ cosets.
We want to bound the size of $A_r$ by an expression that will contradict estimate~(\ref{eq: 3}) above. For each coset $W_s$ let $M_s = M \cap W-s$ and let $a_s$ denote the density $|M_s|/|W_s|$. If $a_s$ is large then only a few elements of $W_s$ can belong to $A_r$ (namely, the complement of $M_s$). If $a_s$ is small then we can use the estimate in~(\ref{eq: 2}) applied to $W_s$ since we chose $|W_s| = |W| = p^m \geq N_0(\varepsilon)$. The $M_s$ with intermediate density are bad; all that can be done is to bound the nubmer of such cosets.
With these remarks in mind we define three different types of cosets:
\begin{align*}
&W_s\textup{ is \emph{dense}} &&\textup{if }a_s > 1 - 1/m, \\
&W_s\textup{ is \emph{bad}} &&\textup{if }1/m |M + rP\setminus M| \geq \sum_{s \textup{ bad}} |M_s + rP\setminus M_s| \geq \frac{B}{|W|} \cdot \frac{2}{p-1} \cdot \frac{1}{m^2}|W| \]
so
\begin{equation} B < \frac{m^3N(p-1)}{2\log^3N} = O\left( \frac{[\log^4N]^3 N}{\log^3N} \right) = o(N). \label{eq: 8} \end{equation}
Combining~(\ref{eq: 8}) with~(\ref{eq: 3}) and~(\ref{eq: 7}) gives
\[ (c - (2p - 1)\varepsilon) \frac{N}{p} < |A_r| < (c + \varepsilon) (1 - c + (2p - 1)\varepsilon) \frac{N}{p} + o(N), \]
where the $o(N)$ term could be written out explicitly if desired. This can be rearranged to say
\begin{align*} c^2 &< \varepsilon (2pc - 2c + 2p) + (2p - 1)\varepsilon^2 + \frac{o(N)}{N} \\
&< 4p\varepsilon + 2p\varepsilon^2 + o(N)/N < 6p\varepsilon + o(N)/N. \end{align*}
It is easy to see that this contradicts the assumptions $\varepsilon < c^2/8p$ and $o(N)/N < c^2/4$ made at the beginning of the proof. Thus the assumption that $c$ is positive is untenable and the proof of the theorem is finished.
\end{proof}
\emph{Remark.} The arbitrary element $r \ne 0,1$ of $F$ can be chosen explicitly (just after the ``Fact" above) to give a slightly stronger result. If $r = 2$ then the proof actually shows that sufficiently large subsets of sufficiently large affine spaces contain three ``equally spaced" collinear points of the form $x, x + y, x + 2y$.
\section{Remarks} \label{sec: 4}
\emph{Possible Generalizations}
\vspace{12pt}
The well-known Hales-Jewett Theorem~\cite{hales+jewett1963} says that for all finite sets $F$ and $r \geq 1$ there is an $n = n(r,F)$ such that if the points of $F^n$ are colored using $r$ colors then there is a monochromatic combinatorial line. (A set $L \subset F^n$ is a \emph{combinatorial line} if $|L| = |F|$ and there is a decomposition $\{1,2,\dots,n\} = S \cup T$ with the following property. For $i$ in $S$ the projection from $L$ onto the $i$th coordinate is a constant mapping (with the constant possibly depending on $i$). For $i$ in $T$ the projection from $L$ onto the $i$th coordinate is a fixed isomorphism $p: L \mapsto F$. One could visualize a combinatorial line as an $|F| \times n$ array of elements of $F$ such that the columns were either constant (with possibly different constants for different columns) or else run through all elements of $F$ in some fixed order.)
One would like to be able to prove the density version of the Hales-Jewett result to the effect that $f(N) = o(N)$, where $f(|F^n|)$ is the size of the largest subset of $F^n$ not containing a combinatorial line.
If we take $|F| = 3$ in the Theorem above then 3 collinear points form an affine line. An affine line in $F^n$ could be viewed as a $3 \times n$ array with columns that are either constant or else run through all of the elements of $F$ in any order. Perhaps one key to extending the proof given above to combinatorial lines would be a drastically improved version of Lemma~\ref{lemma: 1}
A very general Ramsey-type theorem in a geometric context follows from the Hales-Jewett Theorem. This was conjectured by Rota and proved by Graham, Rothschild, and Leeb (see the elegant proof in~\cite{spencer1979}; also~\cite{graham+leeb+rothschild1972,graham+rothschild1971-3,graham+rothschild1971-2,voigt}). It says that for any finite field $F$ there is an $n = n(t,k,r,F)$ such that if the $t$-dimensional affine subspaces of $F^n$ are colored with $r$ colors then some $k$-dimensional subpsace has all of its $t$-dimensional subspaces having the same color. The word ``affine" can be replaced throughout by ``linear" or ``projective."
It is natural to ask for ``density versions" of this theorem or its special cases.
As a matter of further detail, in the $t = 0$ case the Hales-Jewett Theorem actually gives not just a monochromatic $k$-dimensional affine subspace, but in fact a monochromatic ``combinatorial $k$-space" whose definition is a natural extension of the definition of a combinatorial line. Density versions of this result would be very strong; they would imply the $t = 0$ case of the density versions of the geometric theorems.
The case in which $F$ is the set, or field, with $2$ elements provides some weak evidence in favor of these conjectures. The density version of the Hales-Jewett Theorem is true by using Sperner's Lemma~\cite{graham1981} and the density version of the $t = 0$ case of the geometric theorem follows from Lemma~\ref{lemma: 1} immediately.
\begin{corn} For every integer $k$ and every $\varepsilon > 0$ there is an $n(\varepsilon, k)$ such that if $V$ is an $n$-dimensional affine space over $\mathbb{F}_2$, $n \geq n(\varepsilon, k)$, and $A$ is a subset of $V$ with $|A| > \varepsilon |V|$, then $A$ contains a $k$-dimensional affine subspace.
\end{corn}
Note that the main result of this paper is still open for field of order $2^n$, $n > 1$. It seems that it is necessary to find something to replace the role of Lemma~\ref{lemma: 2}.
Finally note that the theorem in Section~\ref{sec: 3} is a density version of a geometric Ramsey Theorem only in the case $|F| = 3$ (since this is the only case in which three collinear points form a complete affine line). In a similar vein one could look at sets that do not contain 4 collinear (or coplanar?) points.
\vspace{12pt}
\emph{An Application to Coding Theory}
\vspace{12pt}
Let $\mathbb{P}^n(F)$ denote the usual $n$-dimensional projective space over a finite field $F$. A subset $A$ of $\mathbb{P}^n(F)$ is said to be an \emph{ovaloid} if it is maximal with respect to the property of not containing 3 collinear points.
Ovaloids can be used to produce codes that can correct one error and detect three; in the cases $n = 2$ and $n = 3$ they have a nice geometrical structure. Little is known about ovaloids in $\mathbb{P}^n(F)$ for $n > 3$ (see~\cite{hill1978} and~\cite{segre1959} and the references therein).
In the case in which $F$ has odd characteristic our main result implies the density of ovaloids must be asymptotically zero. We are grateful to A. Odlyzko and R. Graham for bringing this to our attention.
\begin{prop}
Let $F$ be the field with $q$ elements, $q$ odd. Then for all $\varepsilon > 0$ there is an $n(\varepsilon)$ such that if $n$ is larger than $n(\varepsilon)$ and $A$ is an ovaloid in $\mathbb{P}^n(F)$ then $|A| < \varepsilon |\mathbb{P}^n(F)|$.
\end{prop}
\begin{proof}
Let $n_0$ be the integer such that if $n \geq n_0$ then any subset of $F^n$ of density bigger than $\varepsilon / 2$ must contain 3 collinear points; the existence of $n_0$ is guaranteed by the theorem in Section~\ref{sec: 3}. Define
\[ n(\varepsilon) = n_0 + \log_q(2/\varepsilon), \]
where $\log_q$ denotes logarithm to the base $q$.
It is a standard fact that projective space can be decomposed into a union of affine spaces as
\[ \mathbb{P}^n(F) \cong F^n \cup F^{n-1} \cup \cdots \cup F^1 \cup F^0. \]
If $A$ is an ovaloid in $\mathbb{P}^n(F)$ and $n \geq n(\varepsilon)$ then we can crudely estimate the size of $A$ by breaking it into two parts:
\[ |A| = |A \cap (F^n \cup \cdots \cup F^{n_0})| + |A \cap (F^{n_0 - 1} \cup \cdots \cup F^0)|. \]
Use the definition of $n_0$ for the first term and include the whole subset in the second term; the result is
\[ |A| \leq \frac{\varepsilon}{2} (q^n + \cdots + q^{n_0}) + (q^{n_0 - 1} + \cdots + 1). \]
After summing the geometric series and using the definition of $n(\varepsilon)$ we get $|A|/ |\mathbb{P}^n(F)| < \varepsilon$ as desired. This finishes the proof of the Proposition.
\end{proof}
It is clear that the estimates on the size of line-free sets implied by the above proposition (which depend on the estimates implicit in the proof of the Theorem in Section~\ref{sec: 3}) are very poor. It would be interesting to describe the size of ovaloids (or line-free sets in $F^n$) more accurately. In order describe the known values in the case $F = \mathbb{F}_3$ let $f(n) = $ the size of the maximal line-free set in $F^n$ and let $g(n) = $ the size of the maximal line-free set in $\mathbb{P}^n(F)$ (i.e., the size of an ovaloid). By various calculations (see~\cite{hill1978} for the case of ovaloids) the following values are known:
\begin{align*}
&f(1) = 2, &&g(1) = 2, \\
&f(2) = 4, &&g(2) = 4, \\
&f(3) = 9, &&g(3) = 10, \\
&f(4) = 20, &&g(4) = 20, \\
&f(5) \geq 45, &&g(5) = 56 \end{align*}
(the inequality is almost certainly an equality).
\nocite{alspach+brown+hell1976,brown1975-3}
\bibliographystyle{amsplain}
\bibliography{tom-all}
\end{document}