%%%% THIS FILE IS AUTOMATICALLY GENERATED
%%%% DO NOT EDIT THIS FILE DIRECTLY,
%%%% ONLY EDIT THE SOURCE, tom-43/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}{Remarks}
\newtheorem*{app}{Applications}
\newtheorem*{conj}{Conjecture}

\title{Lines Imply Spaces in Density Ramsey Theory}
\author{T. C. Brown and J. P. Buhler}
\date{}
\maketitle
\begin{center}{\small {\bf Citation data:} T.C. Brown and J.P. Buhler, \emph{Lines imply spaces in density Ramsey theory}, J. Combin. Theory
  Ser. A \textbf{36} (1984), 214--220.}\bigskip\end{center}

\begin{abstract} 
Some results of geometric Ramsey theory assert that if $F$ is a finite field (respectively, set) and $n$ is sufficiently large, then in any coloring of the points of $F^n$ there is a monochromatic $k$-dimensional affine (respectively, combinatorial) subspace (see~\cite{spencer1979}). We prove that the density version of this result for lines (i.e., $k = 1$) implies the density version for arbitrary $k$. By using results in~\cite{brown+buhler1982,graham+rothschild+spencer1980} we obtain various consequences: a ``group-theoretic" version of Roth's Theorem, a proof of the density assertion for arbitrary $k$ in the finite field case when $|F| = 3$, and a proof of the density assertion for arbitrary $k$ in the combinatorial case when $|F| = 2$.
\end{abstract} 

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

In this section we will state and discuss the main results and prove some corollaries. The proofs of the main results are in the following section. Throughout $q$ denotes a prime power.

Let $\mathbb{F}_q$ be the field with $q$ elements and let $V$ be an $n$-dimensional vector space over $\mathbb{F}_q$. For each positive integer $k$ and positive real number $\varepsilon$ let $n(\varepsilon, k, q)$ denote the smallest integer (if one exists) such that
\[ n = \dim_{\mathbb{F}_q} V \geq n(\varepsilon, k, q), \quad A \subset V, \quad |A| > \varepsilon |V|, \]
imply that $A$ contains an affine $k$-space. (By an affine $k$-space we mean any translate of a $k$-dimensional vector subspace; the purist will note that we only use the structure of $V$ as an affine space.)

The ``Affine Line Conjecture" is the assertion that $n(\varepsilon, 1, q)$ exists for all $\varepsilon > 0$ and all $q$. The existence of $n(\varepsilon, k, q)$ would be a density version of the results in~\cite{spencer1979} on Ramsey theorems in geometric contexts. 

The main assertion of this paper is that if, for a fixed $q$, $n(\varepsilon, 1, q)$ exists for all $\varepsilon > 0$, then $n(\varepsilon, k, q)$ exists for all $k$ and all $\varepsilon > 0$. We will also reinterpret this result in the context of ``combinatorial" $k$-spaces and ``lattices" in abelian groups. We include a number of corollaries and remarks.

(It is not hard to see that if $n(\varepsilon, 1, q)$ exists for all $\varepsilon > 0$ and \emph{all} $q$, then $n(\varepsilon , k, q)$ exists for all $k, \varepsilon$, and $q$. Indeed, if $\varepsilon, k$, and $q$ are given, let $F$ be the extension of $\mathbb{F}_q$ of degree $k$. An affine line in an $F$-vector space is a $k$-space over $\mathbb{F}_q$ if we ``restrict scalars" to $\mathbb{F}_q$; from this it is easy to see that the existence of an affine line in a large enough subset of $F^n$ implies the existence of an affine $k$-space in a large enough subset of $\mathbb{F}_q^{kn}$.)

\begin{thm} \label{thm: 1} 
Suppose that $\mathbb{F}_q$ is a fixed finite field and that $n(\varepsilon, 1, q)$ exists for all $\varepsilon > 0$. Then $n(\varepsilon, k, q)$ exists for all $\varepsilon > 0$ and all $k$.
\end{thm}

\begin{cor} The integers $n(\varepsilon, k, 2)$ and $n(\varepsilon, k, 3)$ exist for all $\varepsilon > 0$ and all $k$.
\end{cor}

\begin{proof}[Proof of the corollary]
Any two-element subset of an $\mathbb{F}_2$ vector space is an affine line so it is trivial that $n(\varepsilon, 1, q)$ exists. The theorem then implies that $n(\varepsilon, k, 2)$ exists for all $k$ (see the corollary to Lemma 1 in~\cite{brown+buhler1982} for a different proof of the existence of $n(\varepsilon, k, 2)$). The existence of $n(\varepsilon, k, 3)$ follows from Theorem~\ref{thm: 1} and the existence of $n(\varepsilon, 1, 3)$ which is the central result of~\cite{brown+buhler1982}. This finishes the proof of the corollary.
\end{proof}

A set $\{x_1,\dots,x_k\}$ of the elements in an abelian group $G$ is said to be independent if $c_1x_1 + c_2x_2 + \cdots = c_k x_k = 0$ implies that $c_i x_i = 0$ for each $i$. An $(m,k)$-lattice in an abelian group $G$ is a set of the form
\[ M = \{a + c_1x_1 + \cdots + c_kx_k: c_i = 0,1,\dots,m-1\}, \]
where $a$ is an element of $G$ and the $x_i$ are independent. If $V$ is a vector space over a finite field, then by an $(m,k)$-lattice in $V$ we mean an $(m,k)$-lattice in its underlying additive group.]

Let $n'(\varepsilon, k, q)$ denote the smallest integer (if one exists) such that if 
\[ n = \dim_{\mathbb{F}_q} V \geq n'(\varepsilon, k, q), \quad A \subset V, \quad |A| > \varepsilon |V|, \]
then $A$ contains a $(3,k)$-lattice.

\begin{thm} \label{thm: 2} $n'(\varepsilon, k, q)$ exists for all $\varepsilon > 0$, $k$, and $q$.
\end{thm}

\begin{cor} For each $\varepsilon > 0$ and positive integer $k$ there is an integer $m(\varepsilon, k)$ such that if $G$ is any finite abelian group with more than $m(\varepsilon, k)$ elements and $A$ is any subset of $G$ with more that $\varepsilon |G|$ elements, then there is a $(3,k)$-lattice inside $A$.
\end{cor}

\begin{proof}[Proof of the corollary]
Let $k$ and $\varepsilon$ be given. Choose by Szemer\'{e}di's theorem~\cite{szemeredi1975} a large enough $n$ so that any subset of $\{1,2,\dots,n\}$ with more than $\varepsilon n$ elements contains an arithmetic progression with $3^k$ terms. Choose $m(\varepsilon,k)$ large enough so that any finite abelian group $G$ with more than $m(\varepsilon ,k)$ elements must contain either a cyclic subgroup $H$ of order at least $n$, or a subgroup $H$ which is the direct product of at least $n'(\varepsilon, k, p)$ cyclic groups of order $p$ for some prime $p< n$. 

Now let $G$ be a finite abelian group with more than $m(\varepsilon, k)$ elements and let $A$ be a subset of $G$ with $|A| > \varepsilon |G|$. Let $H$ be the subgroup whose existence is guaranteed by the choice of $m(\varepsilon, k)$. Then $|A \cap a + H| > \varepsilon |H|$ for some coset $a + H$ of $H$. If $H$ is cyclic, then $A - a$ contains the set 
\[ \{a_0 + c_1d + c_2(3d) + \cdots c_k(3^{k-1}d): c_i = 0,1,2\}, \]
where $d$ is the difference of the arithmetic progression whose existence is guaranteed by the choice of $n$ above. If $H$ is the direct product of at least $n'(\varepsilon, k, q)$ cyclic groups of order $p$, then $A - a$ contains
\[ \{a_0 + c_1x_1 + \cdots + c_k x_k: c_i = 0,1,2\} \]
for an independent set of $x_i$. Thus in either case $A$ contains a $(3,k)$-lattice and we are finished.
\end{proof}

\begin{remark} (1) Roth's special case of Szemer\'{e}di's theorem asserts that if $n$ is sufficiently large and $A$ is a subset of $\{1,2,\dots,n\}$ with more than $\varepsilon n$ elements then $A$ contains a set of the form $\{a, a + x, a + 2x\}$. This is equivalent to the case $k = 1$ of the corollary in the case in which $G$ is cyclic. Indeed, it is not hard to check that one has 
\[ m(\varepsilon, 1) \leq n \leq \frac{1}{2} m\left( \frac{\varepsilon}{2}, 1 \right) + 1 \]
(to verify the second inequality consider subsets of the ``first half" of a sufficiently large cyclic group). Thus the corollary could be thought of as a group-theoretic generalization of Roth's Theorem.

(2) Since sufficiently large groups contain large abelian subgroups~\cite{erdos+strauss1976}, we could actually delete the requirement that $G$ be abelian in the statement of the corollary.

(3) If the Affine Line Conjecture is valid, then the results here imply the obvious ``group-theoretic generalization" of Szemer\'{e}di's Theorem: For every $\varepsilon > 0$, $k$, and $l$ there exists an integer $m(\varepsilon, k, l)$ such that if $G$ is any finite abelian group with more than $m(\varepsilon , k, l)$ elements and $A$ is any subset of $G$ with more $\varepsilon |G|$ elements, then there exists an $(l,k)$-lattice in $A$.
\end{remark}


Finally, we remove the algebraic structure on the underlying set, replacing $\mathbb{F}_q$ with an arbitrary finite set. Thus we consider combinatorial subspaces; we briefly recall the definition (see~\cite{graham+rothschild+spencer1980} for further details).

Let $F$ be the finite set $\{0,1,\dots,t-1\}$ with $t$ elements. A subset $W$ of $F^n$ is a \emph{combinatorial $k$-space} if it satisfies the following. There is a partition
\[ \{1,\dots,n\} = B_0 \cup B_1 \cup \cdots \cup B_k \]
such that $B_1, \dots, B_k$ are nonempty. There is a function $f: B_0 \mapsto F$. A function $\bar{f}: F^k \mapsto F^n$ is defined by $\bar{f}(y_1,\dots,y_k) = (x_1,\dots,x_n)$ where
\begin{align*} 
x_i &= f(i) &&\textup{for $i$ in $B_0$}, \\
x_i &= y_j &&\textup{for $i$ in $B_j$}, 1 \leq j \leq k. 
\end{align*}
$W$ is the range of $\bar{f}$.

The definition is complicated, but it captures a notion of subspace when the only structure on $F$ is that of a finite set. We remark that the Hales-Jewett Theorem~\cite{graham+rothschild+spencer1980,hales+jewett1963} asserts that if $n$ is large enough, then in any coloring of $F^n$ there is a monochromatic combinatorial $1$-space (usually called a combinatorial line).

Let $n''(\varepsilon, k, t)$ be the smallest integer (if one exists) such that if
\[ n \geq n''(\varepsilon, k, t), \quad A \subset F^n, \quad |A| > \varepsilon |F^n|, \]
then $A$ contains a combinatorial $k$-space.

\begin{thm} \label{thm: 3}
Let $t$ be fixed. If $n''(\varepsilon, 1, t)$ exists for all $\varepsilon > 0$, then $n''(\varepsilon, k, t)$ exists for all $\varepsilon > 0$ and all $k$.
\end{thm}

\begin{cor} $n''(\varepsilon, k, 2)$ exists for all $\varepsilon > 0$ and all $k$.
\end{cor}

\begin{proof}[Proof of the corollary]
The existence of $n''(\varepsilon, 1,2)$ is a simple consequence of Sperner's Lemma (see~\cite{brown1975-3} or~\cite{graham+rothschild+spencer1980}).
\end{proof}

\begin{remark} (1) In~\cite{brown1975-3} it is shown that if there is a fixed $\varepsilon_0 < 1$ such that $n''(\varepsilon_0, 1, t)$ exists for all $t$, then $n''(\varepsilon, 1, t)$ exists for all $\varepsilon > 0$ and all $t$. The corresponding result for $n(\varepsilon, 1, q)$ is proved in~\cite{brown+buhler1983}.

(2) The existence of $n''(\varepsilon,1,t)$ is a ``density version" of the Hales-Jewett Theorem. Graham has offered a reward for a proof of the existence (or non-existence!) of the numbers $n''(\varepsilon,1,3)$.
\end{remark}

\section{Proofs} \label{sec: 2}

The following lemma contains the crucial idea underlying Theorems~\ref{thm: 1},~\ref{thm: 2}, and~\ref{thm: 3}.

\begin{lemma} Let $\mathbb{F}_q$ be a fixed finite field and $k$ a fixed positive integer. Assume that $n(\varepsilon, 1, q)$ exists for all $\varepsilon >0$. Then for each positive integer $r$, if $n(1/(r + 1),k,q)$ exists then $n(1/r, k + 1,q)$ exists. Similar statements holds for $n'(\varepsilon, k, q)$ and $n''(\varepsilon, k, t)$.
\end{lemma}

\begin{proof} 
We give the proof in the vector space case $n(\varepsilon, k, q)$. The proofs for $n'(\varepsilon, k, q)$ and $n''(\varepsilon, k, t)$ are entirely analogous. In the lattice case $n'(\varepsilon,k,q)$ it is merely necessary to replace ``$k$-space" with ``$(3,k)$-lattice" and ``line" with ``$(3,1)$-lattice" throughout. In the combinatorial case $n''(\varepsilon, k, t)$ it is necessary to replace ``affine $k$-space" with ``combinatorial $k$-space" and ``affine line" with ``combinatorial line" throughout. 

Let $n_0 = n(1/(r + 1),k,q)$. Let $e$ be the number of distinct $k$-dimensional \emph{vector} subspaces of any $n_0$-dimensional vector space over $\mathbb{F}_q$. Let $\delta = (q^{n_0}er^2)^{-1}$ and let $s = n(\delta, 1, q)$. We claim that 
\[ n(1/r, k + 1, q) \leq n_0 + s. \]

To prove this we must start with a vector space $V$ over $\mathbb{F}_q$ of dimension at least $n_0 + s$. Let $A$ be a subset of $V$ with 
\[ |A| > (1/r)|V| \geq (1/r)q^{n_0 + s}. \]
Let $W_0$ be a $n_0$-dimensional subspace of $V$ and let 
\[ V = \bigcup W_\alpha \]
be the decomposition of $V$ into a union of the pairwise disjoint translates (cosets) of $W_0$. For the proof to work in the combinatorial case it is necessary at this point to choose $W_0$ to be the subspace consisting of the vectors whose last $s$ components are $0$.

Let $t$ be the number of cosets $W_\alpha$ such that 
\[ |A \cap W_\alpha| \leq \frac{1}{r + 1} |W_\alpha| = \frac{1}{r + 1}q^{n_0}. \]
There are $q^s$ cosets altogether, so 
\[ \frac{1}{r} |V| < |A| = \sum |A \cap W_\alpha| \leq \frac{t}{r + 1} |W_\alpha| + (q^s - t)|W_\alpha|. \]
This gives 
\[ q^s - t > q^s/r^2. \]
Hence there are $d = q^s - t > q^s / r^2$ cosets $W_\alpha$ such that 
\[ |A \cap W_\alpha| > \frac{1}{r + 1} |W_\alpha|, \]
and since the dimension of $W_0$ is $n_0 = n(1/(r + 1), k, q)$ each such $A \cap W_\alpha$ must contain an affine $k$-space 
\[ a_\alpha + U_\alpha, \]
Where $U_\alpha$ is a $k$-dimensional vector subspace of $W_o$. 

Since there are exactly $e$ distinct $k$-dimensional vector subspaces of $W_0$ at least $d/e$ of the $k$-spaces $a_\alpha + U_\alpha$ must have the form $a_\alpha + U$ for a fixed $U$. Let these be
\[ a_1 + U, \dots,a_h + U, \]
where $h \geq d/e$. 

Let $A' = \{a_1,\dots,a_h\}$. Then 
\[ |A'| = h \geq d/e > \frac{q^s}{er^2} = \frac{1}{q^{n_0}er^2}q^{n_0 + s} = \delta |V|. \]
Since the dimension of $V$ is $n_0 + s > s = n(\delta, 1, q)$, there must be an affine line in $A'$. By renumbering if necessary we can assume that this line is $\{a_1,\dots,a_q\}$.

It is now easy to check that 
\[ U' = (a_1 + U) \cup \cdots \cup (a_q + U) \]
is an affine $(k + 1)$-space contained in $A$. Since $A$ was an arbitrary subset of $V$ with $|A| > (1/r)|V|$ this shows that 
\[ n(1/r, k + 1, q) \leq n_0 + s = \dim_{\mathbb{F}_q}(V) \]
as claimed. This finishes the proof of the lemma.
\end{proof}

Theorem~\ref{thm: 1} now follows immediately from the lemma by induction. Indeed, we are given in the hypotheses of the theorem that $n(\varepsilon, 1, q) $ exists for all $\varepsilon > 0$. If $n(\varepsilon, k, q)$ exists for all $\varepsilon$, then it exists for $\varepsilon = 1/r$. By the lemma, $n(\varepsilon, k + 1, q)$ exists for all $\varepsilon > 0$. Theorem~\ref{thm: 1} now follows by induction on $k$.

The proof of Theorem~\ref{thm: 3} is identical; we merely replace $n(\varepsilon, k, q)$ with $n''(\varepsilon, k ,t)$. 

To prove Theorem~\ref{thm: 2} for odd $q$ we first observe that $n'(\varepsilon, 1, q)$ exists for all $\varepsilon > 0$ as a consequence of the main result in~\cite{brown+buhler1982}. For this case Theorem~\ref{thm: 2} follows from the lemma and induction as above. 

To prove Theorem~\ref{thm: 2} for even $q$ we observe that a $(3,k)$-lattice is just a $(2,k)$-lattice since $2 = 0$ in $\mathbb{F}_q$. It then follows that $n'(\varepsilon, 1, q)$ exists since any two elements of an abelian group form a $(2,1)$-lattice. The rest of the proof is as above. (An upper bound for $n'(\varepsilon, k, q)$ for even $q$ can also be deduced from Lemma 1 in~\cite{brown+buhler1982}.)

\vspace{12pt}

\emph{Note added in proof.} The lemma can be easily improve to show that $n(1/r, k + 1, q) \leq n(1/(r + 1), k, q) + n(1/(er^2), 1, q)$.

\nocite{graham+rothschild1971-2,roth1952}


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