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

\title{Behrend's Theorem for Dense Subsets of Finite Vector Spaces}
\author{T. C. Brown and J. P. Buhler}
\date{}
\maketitle
\begin{center}{\small {\bf Citation data:} T.C. Brown and J.P. Buhler, \emph{{Behrend}'s theorem for dense subsets of finite vector spaces},
  Canad. J. Math. \textbf{35} (1983), 724--734.}\bigskip\end{center}

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

The ``combinatorial line conjecture" states that for all $q \geq 2$ and $\epsilon > 0$ there exists $N(q,\epsilon)$ such that if $n \geq n(q,\epsilon)$, $X$ is a $q$-element set, and $A$ is any subset of $X^n$ ($=$ cartesian product on $n$ copies of $X$) with more than $\epsilon |X^n|$ elements (that is, $A$ has density greater than $\epsilon$), then $A$ contains a combinatorial line. (For a definition of combinatorial line, together with statements and proofs of many results related to the combinatorial line conjecture, including all those results mentioned below, see~\cite{graham+rothschild+spencer1980}. Since we are not directly concerned with combinatorial lines in this paper, we do not reproduce the definition here.)

This conjecture (which is a strengthened version of a conjecture of Moser~\cite{moser1970}), if true, would bear the same relation to the Hales-Jewett theorem that Szemer\'{e}di's theorem bears to van der Waerden's theorem. In particular, it would imply Szemer\'{e}di's theorem. The conjecture is known to be true for the case $q = 2$ (see~\cite{graham+rothschild+spencer1980} or~\cite{brown1975-3}), as was first observed by R. L. Graham. A reward has been offered by Graham for a proof or disproof of the conjecture for the case $q = 3$.

A natural weakening of this (apparently very difficult) conjecture is obtained by replacing the integer $q$ by a prime power $q$, the $q$-element set $X$ by the $q$-element field $F_q$, the cartesian product $X^n$ by an $n$-dimensional vector space $V$ over $F_q$, and ``combinatorial line in $X^n$" by ``affine line in V". (An affine line is any translate of a 1-dimensional vector subspace; the purist will note that we only use the structure of $V$ as an affine space.)

We thus obtain the ``affine line conjecture:" For every prime power $q$ and $\epsilon > 0$, there exists $n(q,\epsilon)$ such that if $n \geq n(q,\epsilon)$, $V$ is an $n$-dimensional vector space over the $q$-element field, and $A$ is any subset of $V$ with more than $\epsilon |V|$ elements (that is, $A$ has density greater than $\epsilon$), then $A$ contains an affine line.

The affine line conjecture is known to be true for the cases $q = 2$ (trivial) and $q = 3$~(\cite{brown+buhler1982}). In~\cite{brown+buhler1984} it is shown that if the affine line conjecture is true for a given fixed value of $q$, then it remains true for this value of $q$ when ``affine line" is replaced by ``$k$-dimensional affine subspace", for any $k$, and similarly for the combinatorial line conjecture.

Szemer\'{e}di's theorem~\cite{szemeredi1975} states that for each $k$ and $\epsilon > 0$, there exists $n$ such that if $A$ is any subset of $\{1,2,\dots,n\}$ with more than $\epsilon n$ elements (that is, $A$ has density greater than $\epsilon$), then $A$ contains a $k$-term arithmetic progression. Some 37 years prior to the proof of Szemer\'{e}di's theorem, Felix Behrend~\cite{behrend1938} proved the following result: If Szemer\'{e}di's theorem is false then there exist triples $(k,n,A)$ such that $A$ is a subset of $\{1,2,\dots,n\}$ which contains no $k$-term arithmetic progression, $n$ is arbitrarily large, and the density of $A$ in $\{1,2,\dots,n\}$ $(=|A|/n)$ is arbitrarily close to 1.

In~\cite{brown1975-3}, the exact analogue of Behrend's result was established in the context of the combinatorial line conjecture: If the combinatorial line conjecture is false then there exist triples $(X,n,A)$ such that $X$ is a finite set, $A$ is a subset of $X^n$ which contains no combinatorial line, $n$ is arbitrarily large, and then density of $A$ in $X^n$ $(=|A|/|X^n|)$ is arbitrarily close to 1.

In the present paper we show that the exact analogue of Behrend's result is true in the context of the affine line conjecture: If the affine line conjecture is false then there exist triples $(F,n,A)$ such that $F$ is a finite field, $A$ is a subset of $F^n$ (the $n$-dimensional vector space over $F$) which contains no affine line, $n$ is arbitrarily large, and the density of $A$ in $F^n$ $(|A|/|F^n|)$ is arbitrarily close to 1.

The proof is somewhat technical, and the exact result which we prove is following. Suppose that the affine line conjecture fails for the finite field $F$. (That is, let $|F| = q$ and suppose that $n(q,\epsilon)$ does not exist for some $\epsilon > 0$.) Then for every $\eta < 1$ and every $n_0$ there is a subset $A$ of a finite-dimensional vector space $V$ over a finite extension $F'$ of $F$, where $\dim_{F'} V \geq n_0$, such that $A$ contains no affine line and the density of $A$ in $V$ $(=|A|/|V|)$ is greater than $\eta$.

The proof is basically a modification of the argument in~\cite{brown1975-3}, which in turn followed the lines of the classical paper by Behrend~\cite{behrend1938}.

\section{Notation, definitions, and statement of the main theorem} \label{sec: 2}

Throughout, $F_q$ denotes the $q$-element field.

\begin{defn} For each prime power $q$ and $\epsilon > 0$, $n(q,\epsilon)$ denotes the smallest integer (if one exists) such that if $V$ is a finite-dimensional vector space over $\mathbb{F}_q$, $\dim(V) \geq n(q,\epsilon)$, $A \subset V$, $|A| > \epsilon |V|$, then $A$ contains an affine line.
\end{defn}

For a fixed prime power $q$, consider the infinite array 
\[ m(q) = (d(n,k)) \quad (n \geq 1, k \geq 1) \]
where the rows are indexed by $n$ and the columns are indexed by $k$, and where $d(n,k)$ is defined as follows. Let $V$ be an $n$-dimensional vector space over $\mathbb{F}_{q^k}$ and let $A$ be a subset of $V$ that has maximum cardinality subject to the condition that $A$ contains no affine line. Then 
\[ d(n,k) = |A|/|V|. \]
In other words, $d(n,k)$ is the smallest real number with the following property. If $B$ is any subset of $V$ ($V$ as above) with $|B| > d(n,k) |V|$, then $B$ contains an affine line.

\begin{remark} It follows directly from the preceding two sentences and the definition of $n(q,\epsilon)$ that for all $n,k$,
\[ n \geq n(q^k,\epsilon) \quad \textup{if and only if} \quad d(n,k) \leq \epsilon. \]
\end{remark}

We shall see below that each column of the array $M(q)$ decreases. We define, for each $k \geq 1$, 
\[ \gamma(k) = \lim_{n \to \infty} d(n,k), \]
so that 
\[ d(1,k) \geq \cdots \geq d(n,k) \geq \cdots \geq \gamma(k). \]
We shall also see that for each row of $M(q)$,
\[ d(n,1) \leq d(n,2) \leq d(n,4) \leq \cdots \leq d(n,2^l) \leq \cdots \leq 1, \]
so that 
\[ 0 \leq \gamma(1) \leq \cdots \leq \gamma(2^lk) \leq \cdots \leq \Gamma(q), \]
where by definition
\[ \Gamma(q) = \lim_{l \to \infty} \gamma(2^l). \]

\begin{thm} 
$\Gamma(q) = 0$ or $\Gamma(q) = 1$.
\end{thm}

\begin{cor} Suppose the affine line conjecture is false. In particular, suppose that $n(q,\epsilon)$ does not exist. Let $\eta < 1$ be given. Then there exists an integer $k$ and a subset $A$ of a finite-dimensional vector space $V$ (of arbitrarily large dimension) over $\mathbb{F}_{q^k}$ such that $A$ contains no affine line and $A$ has density greater than $\eta$.
\end{cor} 

\begin{proof}[Proof of Corollary]
We prove the contrapositive. We are assuming that (as is shown in Lemma~\ref{lemma: 1} below) $d(n,k)$ decreases to $\gamma(k)$ and that $\gamma(2^l)$ increases to $\Gamma(q)$.

Now let $q$ and $\eta < 1$ be given, and suppose that for each $k \geq 1$, if $A$ is a subset of a vector space $V$ over $\mathbb{F}_{q^k}$ with density greater than $\eta$, and $\dim V$ is sufficiently large, then $A$ must contain an affine line. In other words, we are assuming that $n(q^k,\eta)$ exists for all $k \geq 1$. We need to show that $n(q,\epsilon)$ exists for all $\epsilon > 0$. 

Construct the array $M(q)$ as above, and consider the entries $d(n,k)$ in the $k$th column of $M(q)$. Since $n(q^k,\eta)$ exists then by the Remark above 
\[ d(n,k) \leq \eta \quad \textup{for all }n \geq n(q^k,\eta). \]
Since $d(n,k)$ decreases to $\gamma(k)$, it follows that $\gamma(k) \leq \eta$, for each $k \geq 1$. In particular, $\gamma(2^l) \leq \eta$ for each $l$; since $\gamma(2^l)$ increases to $\gamma(q)$, it follows that $\Gamma(q) \leq \eta < 1$. By the theorem, we must have $\Gamma(q) = 0$ and hence $\gamma(1) = 0$.

Now let $\epsilon > 0$ be given. Since $d(n,1)$ decreases to $\gamma(1) = 0$, $d(n,1) < \epsilon$ for sufficiently large $n$, say $d(n_0,1) < \epsilon$. Then using the Remark once more, we obtain $n_0 \geq n(q,\epsilon)$. Thus, $n(q,\epsilon)$ exists.
\end{proof}

\section{Proof of the main theorem} \label{sec: 3}

\begin{lemma} \label{lemma: 1} 
Fix $q$, and let the numbers $d(n,k)$ be defined as above. Then 
\[ d(1,k) \geq \cdots \geq d(n,k) \geq d(n + 1,k) \geq \cdots \]
and 
\[ d(n,1) \leq \cdots \leq d(n,2^l) \leq d(n,2^{l + 1}) \leq \cdots . \]
\end{lemma}

\begin{proof} For the first part, let 
\[ \dim_{\mathbb{F}_{q^k}}V = n + 1 \]
and let $V_0$ be an $n$-dimensional subspace of $V$. Let 
\[ V = \bigcup\{V_\alpha: \alpha \in \mathbb{F}_{q^k} \}, \]
where the $V_\alpha$ are cosets (translates) of $V_0$. Let $A$ be a subset of $V$ which has maximum cardinality subject to the condition that $A$ contains no affine line. Then $A \cap V_\alpha$ contains no affine line for each $\alpha$, hence 
\[ d(n + 1, k) \cdot (q^k)^{n + 1} = |A| = \sum |A \cap V_\alpha| \leq q^k \cdot d(n,k) \cdot (q^k)^n. \]
For the second part, let $F = \mathbb{F}_{q^{2^l}}$ and let $F' = F(\beta)$, where $\beta$ has degree 2 over $F$. Let 
\begin{align*} V &= \{(x_1,\dots,x_n): x_i \in F\}, \\
V' &= \{ (x_1 + y_1\beta, \dots,x_n + y_n\beta): x_i,y_i \in F\}, \end{align*}
so that $V \subset V'$.

Let $A$ be an affine-line-free subset of $V$ with 
\[ |A| = d(n,2^l) |V|, \]
and let $A' = A + \beta V$. Then $A'$ is a subset of $V'$, and $A'$ contains no affine line. For if $u_0, v_0, u_1,v_1 \in V$ and 
\[ (u_0 + v_0\beta) + F'(u_1 + v_1\beta) \subset A', \]
then 
\[ u_0 + Fu_1 \subset A. \]
If $u_1 = 0$, we use
\[ \beta^2 = x_1 + y_1\beta, \quad x_1,y_1 \in F, x_1 \ne 0; \]
then $A'$ contains 
\[ (u_0 + v_0\beta) + F\beta(u_1 + v_1\beta) = (u_0 + v_0\beta) + F(u_1\beta + v_1x_1 + v_1y_1\beta). \]
So $A$ contains $u_0 + Fv_1$.
\end{proof}

We now fix some further notation which will be used in the remainder of the proof.

\begin{defn}
For any prime power $q$, $V(q) = \{(x_1,x_2\dots): x \in \mathbb{F}_q$ and $x_i = 0$ for all but finitely many $i\}$, and 
\[ V(q)(m) = \{(x_1,x_2,\dots) \in V(q): x_j = 0, j > m\}. \]
For any subset $S$ of $V(q)$,
\[ S(m) = S \cap V(q)(m) \quad \textup{and} \quad \bar{d}(S) = \limsup_{m \to \infty} |S(m)| \cdot q^{-m}. \]
\end{defn}

\begin{lemma} \label{lemma: 2}
If $S \subset V(q^k)$ and $\bar{d}(S) > \gamma(k)$ (where $\gamma(k)$ is defined in terms of the array $M(q)$)m then $S$ contains an affine line. (That is, $S(m)$ contains an affine line for some $m$.)
\end{lemma}

\begin{proof} Choose $\epsilon > 0$ so that 
\[ \gamma(k) + \epsilon < |S(m)| \cdot q^{-km} \]
for infinitely many $m$. Next, choose $n$ so that 
\[ d(n,k) < \gamma(k) + \epsilon.\]
Finally, choose $m$ so that simultaneously
\[ \gamma(k) + \epsilon < |S(m)| \cdot q^{-km} \quad \textup{and} \quad n < m - n. \]
Assume that $S$ contains no affine line. Then for each $x \in V(q^k)(n)$, $S(m)$ can contain at most $d(m - n, k) \cdot (q^k)^{m - n}$ elements whose first $n$ coordinates agree with the first $n$ coordinates of $x$. Hence
\[ |S(m)| \leq (q^k)^n \cdot d(m-n, k) \cdot (q^k)^{m - n}. \]
Since $d(m - n, k) \leq d(n,k) < \gamma(k) + \epsilon$, this gives
\[ \gamma(k) + \epsilon < |S(m)| q^{-km} < \gamma(k) + \epsilon. \qedhere \]
\end{proof}

\begin{lemma} \label{lemma: 3}
For each $t \geq 1$, if $S \subset V(q^k)$ and $\bar{d}(S) > \gamma(kt)$ (where $\gamma(kt)$ is defined in terms of the array $M(q)$), then $S$ contains a $t$-dimensional affine subspace.
\end{lemma}

\begin{proof} Identify $\mathbb{F}_{q^kt}$ with $\{(x_1,\dots,x_t): x_i \in \mathbb{F}_{q^k}\}$, so that 
\[ V(q^{kt}) = \{((x_1,\dots,x_t), (x_{t + 1}, \dots, x_{2t}), \dots): x_i \in \mathbb{F}_{q^k}\}. \]
Let $S \subset V(q^k)$, $\bar{d}(S) > \gamma(kt)$. Choose $\epsilon > 0$ so that 
\[ |S(m)| \cdot q^{-km} > \gamma(kt) + \epsilon \]
for infinitely many $m$. From amongst these $m$, choose a subsequence $m_{0} < m_1 <m_2 < \cdots$ such that all the $m_i$'s are congruent modulo $t$.

Let $\pi: S \mapsto V(q^k)$ be the mapping which shifts an element of $S$ ``$m_0$ places to the left," i.e.,
\[ \pi (x_1,\dots,x_{m_0}, x_{m_0 + 1}, \dots) = (x_{m_0 + 1}, \dots),. \]
For any $T \subset S$, let $T'$ denote $\pi(T)$.

For each $x = (x_1,\dots,x_{m_0}, 0,\dots) \in V(q^k)(m_0)$, let 
\[ S_x = \{y = (y_1,\dots) \in S: y_i = x_i, 1 \leq i\leq m_0\}. \]
Then $S$ is the disjoint union
\[ S = \bigcup \{S_x: x \in V(q^k)(m_0)\}. \]
Therefore for each $i \geq 1$,
\[ \sum_x |S_x(m_l)| = |S(m_i)| > a^{k m_i} (\gamma(kt) + \epsilon). \]
Hence for some $x_i \in V(q^k)(m_0),$
\begin{align*}
|S_{x_i}'(m_i - m_0)| &= |S_{x_i}(m_i)| \geq q^{-km_0}|S(m_i)| \\
&> q^{k(m_i - m_0)} (\gamma(kt) + \epsilon).
\end{align*}
Since each $x_i$ comes from the finite set $V(q^k)(m_0)$, there is an infinite subsequence $\{m_{i_j}\}$ of $\{m_i\}$ on which $x_{i_j}$ is constant, say $x_{i_1} = x_{i_2} = \cdots = x_0$. Set 
\[ n_j = m_{i_j} - m_0, \quad j \geq 1. \]
Then each $n_j$ is a multiple of $t$, say 
\[ n_j = tb_j \quad \textup{and} \quad |S_{x_o}'(n_j)| > q^{kn_j}(\gamma(kt) + \epsilon),\quad j \geq 1. \]
We now inject $S_{x_0}$ into $V(q^{kt})$ by insertion of parentheses, that is, we define $g: S_{x_0} \mapsto V(q^{kt})$ by 
\[ g(x_1,\dots) = ((x_1,\dots,x_t), (x_{t +1}, \dots, x_{2t}), \dots). \]
Then for each $j \geq 1$,
\[ |g(S_{x_0}')(b_j)| = |S_{x_0}'(tb_j)| = |S_{x_0}'(n_j)| > (q^{kt})^{bj} (\gamma(kt) + \epsilon). \]
This means that in $V(q^{tk})$,
\[ \bar{d}(g(S_{x_0}')) > \gamma(kt). \]
Here, $\gamma(kt)$ is the limit down the $(kt)$th column of the array $M(q)$, which is identical with the $k$th column of the array $M(q^t)$. Thus
\[ g(S_{x_0}') \subset V((q^t)^k) \]
and 
\[ \bar{d}(g(S_{x_0}')) > \gamma(k) \]
(where $\gamma(k)$ is defined in terms of the array $M(q^t)$). Hence by Lemma~\ref{lemma: 2} $g(S_{x_0}')$ contains an affine line. This affine line (the underlying field is $\mathbb{F}_{q^{kt}}$) is easily seen to be the image under $g$ of a $t$-dimensional affine subspace of $S_{x_0}'$ (where the underlying field if $\mathbb{F}_{q^k}$). From the definition of $S_{x_0}'$ it follows that $S$ itself contains a $t$-dimensional affine subspace.
\end{proof}

\begin{lemma} \label{lemma: 4}
There exists $S \subset V(q^k)$ such that $\bar{d}(S) = \gamma(k)$ (where $\gamma(k)$ is defined in terms of the array $M(q)$) and such that $S$ contains no affine line.
\end{lemma}

\begin{proof}
Choose $0=n_0 < n_1 < \cdots$ so that $n_i - n_{i-1} \to \infty$ as $i \to \infty$. For $i \geq 1$, let $A_i \subset V(q^k)(n_i)$ be such that $A_i$ contains no affine line,
\[ |A_i| = a^{kn_i} d(n_i,k) \quad \textup{and} \quad 0 \notin A_i. \]
(If $L$ is some fixed affine line $V(q^k)(n_i)$ and $A \subset V(q^k)(n_i)$ contains no affine line, then for some $a \in L$, $a + A$ does not contain 0.) Let 
\[ B_i = A_i - V(q^k)(n_{i-1}) \quad \textup{and} \quad S = \bigcup B_i, \: \: i \geq 1. \]
Then 
\[ |S(n_i)| \geq |B_i| \geq |A_i| - q^{k n_{i - 1}} = q^{kn_i} d(n_i,k) - (q^k)^{n_{i-1} - n_i}, \]
hence
\[ \bar{d}(S) \geq \gamma(k) = \lim_{t \to \infty} d(n_i,k). \]
The sets $B_i$ are pairwise disjoint, and if $x = (x_1,\dots) \in S$ and $j$ is the largest index with $x_j \ne 0$ then $x \in B_i$, where $n_{i-1} < j \leq n_i$.

Suppose that $S$ contains the affine line $u_1,\dots,u_{q^k}$. Choose $i_0$ minimal so that $u_1,\dots,u_{q^k} \in B_1 \cup \cdots \cup B_{i_0}$. Then there are $u_s$ and $j$, $n_{i_0 - 1} < j \leq n_{i_0}$, such that the $j$th coordinate of $u_s$ is not zero. Since the $j$th coordinates of $u_1,\dots,u_{q^k}$ are either constant or are some permutation of $\mathbb{F}_{q^k}$ at least $q^k - 1$ of $u_1,\dots,u_{q^k}$ are contained in $B_{i_0}$. Suppose $u_1 \notin B_{i_0}$. Let $j'$ be the largest index such that the $j'$th coordinate of $u_1$ is not zero. ($j'$ exists since $u_1 \ne 0$.) Then $j' < n_{i_0 - 1}$, and hence the $j'$th coordinates of $u_2,\dots,u_{q^k}$ are all zero. But since $u_1,\dots,u_{q^k}$ are an affine line, then the $j'$th coordinates are either constant or are a permutation of $\mathbb{F}_{q^k}$.

Thus we have arrived at a contradiction (except in the case $q^k = 2$) and therefore $S$ contains no affine line. (When $q^k = 2$, then $\gamma(1) = 0$. Any singleton set $S = \{x\} \subset V(2)$ has $\bar{d}(S) = 0 = \gamma(1)$, and $S$ contains no affine line.) Since $\bar{d}(S) \geq \gamma(k)$, Lemma~\ref{lemma: 2} gives $\bar{d}(S) = \gamma(k).$
\end{proof}

We now have necessary machinery to prove the main theorem. Recall that for a prime power $q$, $M(q)$ is the array 
\[ ((d(n,k)), \quad \gamma(2^l) = \lim_{n \to \infty} d(n,2^l), \quad \Gamma(q) = \lim_{l \to \infty} \gamma(2^l). \]

\begin{thm} 
For every prime power $q$, $\Gamma(q) = 0$ or $\Gamma(q) = 1$.
\end{thm}

\begin{proof} Fix $q$, and assume that $0 < \Gamma(q) < 1$. Choose $l$ so that 

\begin{equation} 0 < \gamma(2^i). \label{eq: 1} \end{equation}

Using Lemma~\ref{lemma: 4}, choose $S \subset V(q^{2^l})$ so that 
\begin{equation} \bar{d}(S) = \gamma(2^l) \label{eq: 2} \end{equation}
\begin{equation} \textup{$S$ contains no affine line}. \label{eq: 3} \end{equation}

Choose $\epsilon < 0$ so that 

\begin{equation} \Gamma(q) < \frac{\gamma(2^l) - \epsilon}{\gamma(2^l) + \epsilon} - \epsilon. \label{eq: 4} \end{equation}

Choose $n$ so that 
\begin{equation} \left\{ \begin{matrix} A \subset V(q^k)(n) \\ |A| > (\gamma(2^l) + \epsilon)q^{kn} \end{matrix} \right\} \Rightarrow \left\{ \begin{matrix} A \textup{ contains} \\
\textup{an affine line} \end{matrix} \right\}. \label{eq: 5} \end{equation}
Choose $t$ (using the extended Hales-Jewett theorem; see~\cite{graham+rothschild+spencer1980} or~\cite{spencer1979}) so that $t$ is a power of 2 and 
\begin{equation} \left\{ \begin{matrix} T \textup{ is a $t$-dimensional affine subspace} \\ \textup{and $T = T_1 \cup \cdots \cup T_s$, where $s = 2^{q^{kn} - 1}$} \end{matrix} \right\} \Rightarrow \left\{ \begin{matrix} \textup{some $T_i$} \\ \textup{contains an} \\ \textup{affine line} \end{matrix} \right\}. \label{eq: 6} \end{equation}
Set 
\begin{equation} V' = V(q^k) - V(q^k)(n), \quad B_v = (v + V(q^k(n)) \cap S, \quad v \in V'. \label{eq: 7} \end{equation}
Partition $V'$ into $2^{q^{kn}}$ classes $C_\sigma$ as follows.
\begin{equation} C_\sigma = \{v \in V': B_v = v + \sigma\}, \quad \sigma \subset V(q^k)(n). \label{eq: 8} \end{equation}
(Note that $C_\sigma = \{v \in V': B_v = \phi\}$.)

Let 
\[ C = \bigcup \{C_\sigma: \sigma \ne \phi \}, \]
and let
\begin{equation} \bar{d}_{V'}(C) = \limsup_{m \to \infty} (q^{-k})^{(m - n)}|C \cap V'(m)|. \label{eq: 9} \end{equation}

Since 
\[ |C \cap V'(m)| < (\bar{d}_{V'}(C) + \epsilon)q^{k(m - n)} \]
for all but finitely many $m$, and since
\[ |S(m)| > (\gamma(2^l) - \epsilon) q^{-km} \]
for infinitely many $m$ (by~(\ref{eq: 2})), we can choose $m$ so that $n < m$ and 
\begin{equation} (\gamma(2^l) - \epsilon) q^{km} < |S(m)| \label{eq: 10} \end{equation}
\begin{equation} |C \cap V'(m)| < (\bar{d}_{V'}(C) + \epsilon)q^{k(m - n)}. \label{eq: 11} \end{equation}
Using~(\ref{eq: 7}),~(\ref{eq: 3}), and~(\ref{eq: 5}) we get 
\begin{equation} |B_v| \leq (\gamma(2^l) + \epsilon) q^{kn}, \quad v \in V'. \label{eq: 12} \end{equation} 
Note that $m > n$ and 
\[ V(q^k)(m) = \bigcup \{v + V(q^k)(n): v \in V'(m)\}, \]
so that 
\begin{align*} V(q^k)(m) \cap S &= \bigcup \{(v + V(q^k)(n) \cap S: v \in V'(m)\} \\
&= \bigcup \{B_v: v \in V'(m) \textup{ and } B_v \ne \phi\} \\
&= \bigcup \{B_v: v \in V'(m) \cap C\}. \end{align*}
That is,
\begin{equation} S(m) = \bigcup \{B_v: v \in V'(m) \cap C\}. \label{eq: 13} \end{equation}
Now using~(\ref{eq: 10}), (\ref{eq: 13}), (\ref{eq: 12}), (\ref{eq: 11}) we get
\[ (\gamma(2^l) - \epsilon) q^{km} < |S(m)| < (\gamma(2^l) + \epsilon) q^{kn} (\bar{d}_{V'} (C) + \epsilon) q^{k(m - n)}, \]
or 
\[ \frac{\gamma(2^l) - \epsilon}{\gamma(2^l) - \epsilon} - \epsilon < \bar{d}_{V'}(C). \]
Using~(\ref{eq: 4}), this gives
\begin{equation} \Gamma(q) < \bar{d}_{V'} (C). \label{eq: 14} \end{equation}
The integer $t$ was chosen to be a power of 2, say $t = 2^b$, and to satisfy~(\ref{eq: 6}). Since 
\[ \gamma(2^lt) = \gamma( 2^{l + b}) \leq \Gamma(q) < \bar{d}_{V'} (C), \]
it follows from Lemma~\ref{lemma: 3} that $C$ contains a $t$-dimensional affine subspace $T$. We partition the elements of $T$ into $2^{q^{kn} - 1}$ classes $C_\sigma \cap T$, $\sigma \ne \phi$. By~(\ref{eq: 6}), some $C_{\sigma_0} \cap T$, and hence some $C_{\sigma_0}$, contains an affine line $u_1,\dots,u_{q^k}$. Using~(\ref{eq: 8}) and~(\ref{eq: 7}), $u_1 \in C_{\sigma_0}$ implies
\[ u_1 + \sigma_0 = B_{u_1} \subset S. \]
Similarly,
\begin{equation} u_i + \sigma_0 = B_{U_i} \subset S, \quad 1 \leq i \leq q^k. \label{eq: 15} \end{equation}
In particular, taking any element $v_0 \in \sigma_0$ $(\sigma_0 \ne \phi)$, $S$ contains the affine line
\[ u_1 + v_0, \dots,u_{q^k} + v_0, \]
which contradicts~(\ref{eq: 3}).

This contradiction shows that $0 < \Gamma(q) < 1$ is impossible, and complete the proof. \end{proof} 

\nocite{hales+jewett1963}


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

