%%%% 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 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}