%%%% THIS FILE IS AUTOMATICALLY GENERATED
%%%% DO NOT EDIT THIS FILE DIRECTLY,
%%%% ONLY EDIT THE SOURCE, tom-58/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*{spern}{Sperner's Lemma}
\newtheorem*{thm}{Theorem}
\newtheorem{q}{Problem}
\theoremstyle{definition}
\newtheorem*{defn}{Definition}
\newtheorem*{ack}{Acknowledgements}

\title{Behrend's Theorem for Sequences Containing No $k$-Element Arithmetic Progression of a Certain Type}
\author{T. C. Brown}
\date{}
\maketitle
\begin{center}{\small {\bf Citation data:} T.C. {Brown}, \emph{Behrend's theorem for sequences containing no $k$-element
  arithmetic progression of a certain type}, J. Combin. Theory Ser. A
  \textbf{18} (1975), 352--356.}\bigskip\end{center}

\begin{abstract}
Let $k$ and $n$ be positive integers, and let $d(n,k)$ be the maximum density in $\{0,1,2\dots,k^n - 1\}$ of a set containing no arithmetic progression of $k$ terms with first term $a = \sum a_ik^i$ and common difference $d = \sum \epsilon_i k^i$, where $0 \leq a_i \leq k - 1$, $\epsilon_i = 0$ or 1, and $\epsilon_i = 1 \Rightarrow a_i = 0$. Setting $\beta_k = \lim_{n \to \infty} d(n,k)$, we show that $\lim_{k \to \infty} \beta_k$ is either $0$ or $1$.
\end{abstract}

Throughout, we shall use the notation $[a,b) = \{a,a+1,a+2,\dots,b-1\}$, for nonnegative integers $a< b$. Also, if $S$ is a set of nonnegative integers, then $S(m)$ denotes $|S \cap [0,m)|$.

The upper asymptotic density of $S$ will be denoted by $\bar{d}(S)$. Thus
\[ \bar{d}(S) = \limsup_{m \to \infty} m^{-1}S(m). \]
Similarly, the lower asymptotic density of $S$ is 
\[ \underline{d}(S) = \liminf_{m \to \infty} m^{-1}S(m). \]
Let $r_k(n)$ denote the largest cardinal of a subset $A$ of $[0,n)$ such that $A$ contains no arithmetic progression of $k$ terms, and let $\rho_k = \lim_{n \to \infty} n^{-1}r_k(n)$. (This idea was introduced by Erd\H{o}s, Tur\'{a}n, and Szekeres in~\cite{erdos+turan1936}, and then convergence of $n^{-1}r_k(n)$ is shown in~\cite{behrend1938}.) K. F. Roth~\cite{roth1953} proved $\rho_3 = 0$ in 1953 and E. Szemer\'{e}di~\cite{szemeredi1975} has shown that $\rho_k = 0$ for all $k$.

Previous to these results, Felix Behrend~\cite{behrend1938} proved in 1937 that $\lim_{k \to \infty} \rho_k$ equals either $0$ or $1$. In this paper we prove the analogous result where $\rho_k$ is replaced by $\beta_k$, the definition of $\beta_k$ being similar to that of $\rho_k$ except that only arithmetic progressions of a certain type are considered. (At the time of this writing, the only known values for $\beta_k$ are $\beta_1 = \beta_2 = 0$.) The main idea for the proof is taken diresctly from Behrend's paper.

\begin{defn} For each positive integer $k$, a \emph{$k$-diagonal} is an arithmetic progression on $k$ terms with first term $a = \sum a_ik^i$ and common difference $d = \sum \epsilon_ik^i$, where for each $i$, $0 \leq a_i \leq k-1$, $\epsilon_i = 0$ or 1, and $\epsilon_i = 1 \Rightarrow a_i = 0$.
\end{defn}

Note that $k$ integers form a $k$-diagonal if and only if their $k$-ary representations can be put into the rows of a matrix in such a way that each column of the matrix, reading from top to bottom, is either $iii \cdots i$, for some $i$ depending on the column, or $012\cdots k-1$. For example, $\{2,5,8\}$ is a $3$-diagonal which contains no 2-diagonal.

\begin{defn} For positive integers $n,k,$ let 
\[ d(n,k) = k^{-n}|A|, \]
where $A$ is a subset of $[0,k^n)$ which has largest cardinal while not containing any $k$-diagonal.
\end{defn}

Thus for each fixed, $k$, we consider only the intervals $[0,k^n)$, $n = 1,2,\dots,$, the reason for this is that we can think of $[0,k^n)$ as the set of all $n$-tuples on the $k$ symbols $0,1,\dots,k-1$, which seems to be an advantage.

The following lemma is proved in~\cite{alspach+brown+hell1976}.

\begin{lemma} \label{lemma: 1}
For each fixed $k$, $\{d(n,k)\}_{n=1}^\infty$ decreases. For each fixed $n$, $\{d(n,k)\}_{k=1}^\infty$ increases.
\end{lemma}

Using this lemma, we can make the following definition.

\begin{defn}
\begin{align*} \beta_k &= \lim_{n \to \infty} d(n,k), \qquad \textup{for $k = 1,2,\dots$.} \\
\beta &= \lim_{k \to \infty} \beta_k.
\end{align*}
\end{defn}

Note that $0 \leq \beta_1 \leq \beta_2 \leq \beta_3 \leq \cdots \leq \beta \leq 1$.

As remarked earlier, our object is to prove that $\beta$ is 0 or 1. We also remarked that the only currently known values of $\beta_k$ are $\beta_1 = 0$ and $\beta_2 = 0$. The first follows directly from the definition of $\beta_1$. The second follows from observing that if $A \subset [0,2^n)$ then we may regard the elements of $A$ (in binary notation) as characteristic functions of subsets of $\{1,2,\dots,n\}$. It is then easy to see that $A$ contains a $2$-diagonal $\{x,y\}$ if and only if ther corresponding subsets $X$ and $Y$ of $\{1,2,\dots,n\}$ satisfy $X \subset Y$ or $Y \subset X$. It then follows by Sperner's lemma that if $A$ has no 2-diagonal then $|A| \leq \binom{n}{\lfloor n/2 \rfloor}$, and therefore $d(n,2) = 2^{-n} \binom{n}{\lfloor n/2 \rfloor} \to 0$ as $n \to \infty$, that is, $\beta_2 = 0$. 

\begin{lemma} \label{lemma: 2}
If $S$ is a set of nonnegative integers with upper density $\bar{d}(S) > \beta_k$, then $S$ contains a $k$-diagonal.
\end{lemma}

\begin{proof}
Let $\epsilon > 0$ be such that $m^{-1}S(m) > \beta_k + \epsilon$ for infinitely many $m$. Choose $n$ so that $d(n,k) < \beta_k + \epsilon/2$, and now choose $m$ so that $\beta_k + \epsilon < m^{-1}S(m)$ and $m^{-1}k^n < \epsilon/2$. Finally, choose $b$ so that $bk^n \leq m < (b + 1)k^n$. If $S$ contains no $k$-diagonal, then in any interval $[ak^n,(a + 1)k^n)$ $S$ can have density at most $d(n,k)$, that is, 
\[ |S \cap [ak^n,(a + 1)k^n)| \leq k^nd(n,k). \]
Therefore $S(m) \leq S(bk^n) + k^n \leq bk^nd(n,k) + k^n$, hence
\[ \beta_k + \epsilon < m^{-1}S(m) \leq d(n,k) + m^{-1}k^n < \beta_k + \epsilon/2 + \epsilon/2. \]
Therefore $S$ contains a $k$-diagonal.
\end{proof}

\begin{lemma} \label{lemma: 3}
For each $k$ there is a set $S$ with $\bar{d}(S) \geq \beta_k$ which does not contain a $k^2$-diagonal.
\end{lemma}

\begin{proof}
Choose positive integers $n_1<n_2<\cdots$ such that $n_{i+1} - n_i \to \infty$. For each $i$, let $A_i \subset [0,k^{n_i})$ be such that $A_i$ contains no $k$-diagonal and $|A| = k^{n_i}d(n_i,k)$. Let $B_i = A_i \cap [2k^{n_{i-1}}, k^{n_i})$, and let $S = \bigcup_{i=1}^\infty B_i$. Then $k^{-n_i}S(k^{n_i}) \geq k^{-n_i}(k^{n_i}d(n_i,k) - 2k^{n_{i-1}}) \to \beta_k$ (we may assume $k \geq 2$ since $\beta_1 = 0$), hence $S$ has upper density $\beta_k$.

Now because of the size of the gaps between successive blocks $B_i$, no arithmetic progression can intersect more than two of the $B_i$'s. In particular, if $S$ contains a $k^2$-diagonal $D$, then either the first $k$ elements of $D$ belong to some $B_i$, or the last $k$ elements of $D$ belong to some $B_j$ (or both). But the first $k$ elements of a $k^2$-diagonal constitute a $k$-diagonal, and similarly for the last $k$ elements. Since no $B_i$ contains a $k$-diagonal, $S$ can contain no $k^2$-diagonal.
\end{proof}

\begin{lemma} \label{lemma: 4}
(a) If $D = \{a_i: i \in [0,k^{pn})\}$ is a $k^{pn}$-diagonal and $J \subset [0,k^{pn})$ is a $k^n$-diagonal then $D' = \{a_j: j \in J\}$ is a $k^n$ diagonal.

(b) If $D$ is a $k^n$-diagonal and $\ell \in [0,k^n)$ is fixed, then $D' = \{k^na + \ell: a \in D\}$ is a $k^n$-diagonal.
\end{lemma}

\begin{proof} (a) Express each element of $D$ in $k^{pn}$-ary notation, so that $D = \{X_1iX_2i\cdots iX_d: i \in [0,k^{pn})\}$, where each $X_j$ is a block (possibly empty) of $k^{pn}$-ary symbols and $i$ is a single $k^{pn}$-ary symbol running from 0 to $k^{pn} - 1$. Replacing each $k^{pn}$-ary symbols by its equivalent string of $p$ $k^{pn}-1$-ary symbols, we obtain $D = \{X_1'i'X_2'i'\cdots i'X_d': i \in [0,k^{pn})\}$, where each $X_j'$ is a block of $k^n$-ary symbols and $i'$ is a block of $p$ $k^n$-ary symbols running from $0$ to $k^{pn} - 1$. It is now clear that if $J$ is a $k^n$-diagonal contained in $[0,k^{pn})$ then so is $D' = \{X_1'jX_2'j \cdots jX_d': j \in J\}$.

(b) If $D = \{X_1iX_2i \cdots iX_d: i \in [-,k^n)\}$ (each element of $D$ is expressed in $k^n$-ary notation), then $D' = \{X_1iX_2i\cdots iX_d\ell: i \in [0,k^n)\}.$
\end{proof}

The following lemma is proved in~\cite{graham+rothschild1971-2} and~\cite{hales+jewett1963}.

\begin{lemma} \label{lemma: 5} 
If $k,c$ are positive integeres then there is an integer $N(k,c)$ such that if $m \geq N(k,c)$ and $[0,m)$ is partitioned in any way into $c$ classes, then at least one class contains a $k$-diagonal.
\end{lemma}

We are now ready to prove the main theorem.

\begin{thm} $\beta$ equals 0 or 1.
\end{thm}

\begin{proof} 
Suppose $0 < \beta < 1$, and choose $k$ so that $\beta_k \cdot (1/\beta) > \beta_{k^2}$. Next choose $\epsilon > 0$ so that $\epsilon < \frac{1}{4} ( \beta_k - \beta\beta_{k^2})$, and using Lemma~\ref{lemma: 3} let $S$ be a set of nonnegative integers with $\bar{d}(S) \geq \beta_k$ which contains no $k^2$-diagonal. Next, choose $n$ large enough that if $A \subset [0,k^{2n})$ and $|A| > (\beta_{k^2} + \epsilon)k^{2n}$ then $A$ must contain a $k^2$-diagonal. For each $j = 0,1,\dots$ let $B_j = S \cap [jk^{2n},(j+1)k^{2n})$. We now partition the nonnegative integers $j$ into $2^{k^{2n}}$ classes as follows. For each $\sigma \subset [0,k^{2n})$, $j$ belongs to the class $C_\sigma$ if and only if $B_j$ is a translate of $\sigma$.

There are now two main steps in the proof. The first is to show that $\bar{d}\left( \bigcup_{\sigma \ne \phi} C_\sigma \right) > \beta$; the second is, using this, to extract a $k^2$-diagonal from $S$, contrary to our initial assumption. 

To show that $\bar{d}\left(\bigcup_{\sigma \ne \phi} C_\sigma \right) > \beta$, we will show that $\underline{d}(C_\phi) < 1- \beta$. Let $\underline{d}(C_\phi) = \xi$, and choose $m$ so that $C_\phi(m) > (\xi - \epsilon)m$ and $S(mk^{2n}) > (\beta_k - \epsilon)mk^{2n}$. Then $\left(\bigcup_{\sigma \ne \phi} C_\sigma \right)(m) < (1 - \xi + \epsilon)m$, and for every $j$, $|B_j| \leq (\beta_{k^2} + \epsilon)k^{2n}$.

Hence
\begin{align*} 
S(mk^{2n}) &= \left| \bigcup \left\{B_j: j \in [0,m) \cap \left( \bigcup_{\sigma \ne \phi} C_\sigma \right) \right\} \right| \\
&< (\beta_{k^2} + \epsilon)k^{2n} \cdot (1 - \xi + \epsilon)m,
\end{align*}
hence
\[ \beta_k - \epsilon < (\beta_{k^2} + \epsilon)(1 - \xi + \epsilon), \]
\begin{align*}
\xi &\leq [(1 + \epsilon)(\beta_{k^2} + \epsilon) - \beta_k + \epsilon]/(\beta_{k^2} + \epsilon) \\
&< (\beta_{k^2} - \beta_k + 4\epsilon)/\beta_{k^2} < 1 - \beta, \end{align*}
by the choice of $\epsilon$. This completes the first step.

For the final step in the proof, choose by Lemma~\ref{lemma: 5} an integer $p$ large enough that if $[0,k^{2pn})$ is partitioned into $2^{k^{2n} - 1}$ classes, then at least one class will contain a $k^{2n}$-diagonal. Since we now know that $\bar{d}\left(\bigcup_{\sigma \ne \phi}C_\sigma \right) > \beta \geq \beta_{k^{2pn}}$, it follows from Lemma~\ref{lemma: 2} that $\bigcup_{\sigma \ne \phi} C_\sigma$ contains a $k^{2pn}$-diagonal $D = \{a_i: i \in [0,k^{2pn})\}$. Let us now partition the indices $i$ of the elements of $D$ into classes $C_\sigma'$ according to the rule $i \in C_\sigma' \Leftrightarrow a_i \in C_\sigma$. Then by the choice of $p$ there is a $k^{2n}$-diagonal $J \subset [0,k^{2pn})$ which is contained in a single class, say $J \subset C_{\sigma_0}'$. This means that $D' = \{a_j:j \in J\}$. is contained in $C_{\sigma_0}$. But by Lemma~\ref{lemma: 4}(a), $D'$ is a $k^{2n}$-diagonal. Thus we now have that the $k^{2n}$ sets $B_{a_j} = S \cap [a_jk^{2n},(a_j + 1)k^{2n})$, $j \in J$, are all translates of $\sigma_0$, and $D' = \{a_j: j \in J\}$ is a $k^{2n}$-diagonal. Since $\sigma_0 \ne \phi$, we may choose $\ell \in \sigma_0$. Then $D'' = \{k^{2n}a_j + \ell: j \in J\} \subset S$, and by Lemma~\ref{lemma: 4}(b) $D''$ is a $k^{2n}$-diagonal. But then the first $k^2$ elements of this $k^{2n}$-diagonal are a $k^2$-diagonal in $S$, contrary to assumption.

Thus the proof is complete.
\end{proof}

\nocite{szemeredi1969}


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