%%%% THIS FILE IS AUTOMATICALLY GENERATED
%%%% DO NOT EDIT THIS FILE DIRECTLY,
%%%% ONLY EDIT THE SOURCE, tom-54/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}
\newtheorem*{lemma}{Lemma}
\newtheorem{thm}{Theorem}
\newtheorem{prop}{Proposition}
\newtheorem{q}{Problem}
\theoremstyle{definition}
\newtheorem{defn}{Definition}
\newtheorem{fact}{Fact}
\newtheorem*{remark}{Remarks}
\newtheorem*{app}{Applications}
\newtheorem*{conj}{Conjecture}
\title{On the Density of Sets Containing No $k$-Element Arithmetic Progression of a Certain Kind}
\author{Brian Alspach, T. C. Brown, and Pavol Hell}
\date{}
\maketitle
\begin{center}{\small {\bf Citation data:} B.~Alspach, T.C. Brown, and P. Hell, \emph{On the density of sets containing no
$k$-element arithmetic progressions of a certain kind}, J. London Math. Soc.
(2) \textbf{13} (1976), 226--234.}\bigskip\end{center}
\section{Introduction} \label{sec: 1}
A theorem now known as Sperner's Lemma~\cite{sperner1928} states that a largest collection of subsets of an $n$-element set such that no subset contains another is obtained by taking the collection of all the subsets with cardinal $\lfloor n/2 \rfloor$. (We denote by $\lfloor x \rfloor$, resp. $\lceil x \rceil$, the largest integer less than or equal to $x$, resp. the smallest integer greater than or equal to $x$.) In other words, the density of a largest antichain in the set of all subsets of an $n$-element set is
\[ 2^{-n} \binom{n}{\lfloor n/2 \rfloor}. \]
The generalization of this problem which is considered here was mentioned to one of the authors by R. L. Graham. An antichain in an $n$-element set can be viewed as a collection of sequences of length $n$ on the symbols $0,1$ such that no two sequences occur which are, in some order, the rows of a $2 \times n$ matrix in which each column is either constant of is
\[ \begin{matrix} 0\\1 \end{matrix}. \]
We now enlarge the set of symbols as follows: Let $A(n,k)$ denote the set of all sequences of length $n$ of the $k$ symbols $0,1,2\dots,k-1$. A subset $K$ of $A(n,k)$ is called a \emph{diagonal of } $A(n,k)$, or simply a \emph{diagonal} if $n$ and $k$ are clear from the context, if $|D| = k$ and the elements of $D$ are the rows (in some order) of a $k \times n$ matrix in which each column is either \emph{constant} or is
\[ \begin{matrix} 0 \\ 1 \\ \vdots \\ k - 1\end{matrix} . \]
Let us call a set $B \subset A(n,k)$ a \emph{good subset of }$A(n,k)$ if $B$ contains no diagonal of $A(n,k)$, and let $d(n,k)$ be the density in $A(n,k)$ of a largest good subset of $A(n,k)$. That is,
\[ d(n,k) = k^{-n} \max\{|B|: B \textup{ is a good subset of }A(n,k)\}. \]
Note that Sperner's Lemma says
\[ d(n,2) = 2^{-n} \binom{n}{\lfloor n/2 \rfloor}; \]
therefore $d(n,2) \to 0$ as $n \to \infty$, by Stirling's Formula.
Let $M$ be the infinite matrix whose entry in the $n$-th row and the $k$-th column is $d(n,k)$. The first column ($k = 1$) of $M$ consists of zeros only; Sperner's Lemma describes the second column. The most important question related to $M$ appears to be whether or not all the column limits are zero, i.e., whether $d(n,k) \to 0$ as $n \to \infty$ (the answer is yes for $k = 1,2$). This is the question posed by Graham. If, in fact, $d(n,k) \to 0$ as $n \to \infty$, then any set of positive integers of positive upper asymptotic density contains an arithmetic progression (of a certain type) with $k$ terms. This may be seen by regarding the elements of $A(n,k)$ as $k$-ary representations of integers. A diagonal of $A(n,k)$ is then an arithmetic progression of a particular kind: the first term is $\sum a_ik^i$ and the common difference is $\sum \varepsilon_i k^i$ where, for each $i, 0 \leq a_i \leq k - 1$ and $a_i = 0$ if $\varepsilon_i = 1$. Szemer\'{e}di proved~\cite{szemeredi1975} that every set of integers of positive upper asymptotic density contains arbitrarily long arithmetic progressions. It is shown below that the sequence of the column limits of the matrix $M$ is increasing, and has a limit. If this limit is 0, then all column limits are zero, and Szemer\'{e}di's theorem would follow. On the other had, it is shown in~\cite{brown1975-3}, that the limit is either 0 or 1. The following result, which is weaker than the convergence to zero of each column, is known~\cite{graham+rothschild1971-2,hales+jewett1963}: given positive integers $r,k$ there exists an integer $n = n(k,r)$ such that if the elements of $A(n,k)$ are partitioned into $r$ classes, then at least one of these classes contains a diagonal.
This paper is concerned with the behavior of $M$ along paths other than columns, i.e., the behavior of sequences $\{d(\phi(k),k)\}$ where $\phi$ is a function of the set of positive integers into itself. In particular, we prove that the \emph{limit along any path in $M$ that lies entirely above a non-vertical line} (i.e., $\phi(k) \leq mk$ for all $k$) is 1.
\section{Elementary results} \label{sec: 2}
If a diagonal $D$ of $A(n,k)$ is written as a $k \times n$ matrix with constant and increasing columns, the latter are called running columns. For example, $D = \{012010, 212210, 112110\}$ is a diagonal in $A(6,3)$ since the elements of $D$ are the rows of the $3 \times 6$ matrix
\[ \begin{matrix} &0 &1 &2 &0 &1 &0 \\ &1 &1 &2 &1 &1 &0 \\ &2 &1 &2 &2 &1 &0 \end{matrix} \]
(here the first and fourth columns are running and the others are constant columns). We shall often identify a diagonal with its corresponding matrix, and shall agree to list the elements of a diagonal in the order they appear as rows of the matrix, e.g., $D = \{012010, 112110, 212210\}$.
The limit along any row of $M$ is 1 (i.e., $d(n,k) \to 1$ as $k \to \infty$ for a fixed $n$), as can be seen from the inequalities
\[ (1 - 1/k)^n \leq d(n,k) \leq 1 - 1/k. \]
To prove the first of these inequalities we observe that $A(n, k -1)$ is a good subset of $A(n,k)$; the second one follows from the fact that there exist $k^{n-1}$ pairwise disjoint diagonals
\[ D = \{a_1a_2\cdots a_{n-1}0, a_1a_2\cdots a_{n-1}1, \dots, a_1a_2\cdots a_{n-1}(k-1) \} \]
(one for each $a_1a_2\cdots a_{n-1} \in A(n-1,k)$), and so any good subset $B$ of $A(n,k)$ can have at most $k^n - k^{n-1}$ elements.
It follows from the above remarks that the limit of the row limits exists and is equal to 1. We proceed to examine the existence of the column limits and of their limit.
\begin{prop} \label{prop: 1}
In the matrix $M$, each row is an increasing sequence, and each column a decreasing sequence.
\end{prop}
\begin{proof} To show that the $n$-th row of $M$ is increasing, let $B$ be a good subset of $A(n,k)$ of maximum cardinal. In order to obtain $d(n,k) \leq d(n, k + 1)$ it is sufficient to construct a good subset $C$ of $A(n, k + 1)$ such that the central inequality of the following line holds:
\[ d(n,k) = k^{-n}|B| \leq (k + 1)^{-n}|C| \leq d(n,k + 1). \]
That is, we require a good subset $C$ of $A(n,k + 1)$ satisfying
\[ (1 + 1/k)^n|B| \leq |C|. \]
To achieve this we shall proceed by induction. The set $C_0 = B$ has the following properties ($j = 0$):
(1) $C_j$ is a good subset of $A(n,k+1)$.
(2) $(1 + 1/k)^j|B| \leq |C_j|$.
(3) If the new symbol $k$ (the old symbols are $0,1,\dots,k-1$) appears in the $i$-th entry of a sequence in $C_j$, then $i \leq j$. Furthermore, for each $i \leq j$ there is a \emph{unique} symbol $u_i$ difference from $k$, such that if $a_1a_2 \cdots a_{i-1}ka_{i + 1} \cdots a_n \in C_j$ then $a_1a_2 \cdots a_{i-1}u_ia_{i+1} \cdots a_n \in C_j$.
(4) If $a_1a_2\cdots a_n \in C_j$ and no $a_i = k$, then $a_1a_2 \cdots a_n \in B$.
If $C_j$, $0 \leq j < n$ satisfies (1)--(4), we construct $C_{j + 1}$ as follows: In the $(j + 1)$-st entry of the sequences of $C_j$ some symbol, say $a$, occurs at least $(1/k) |C_j|$ times. Let $P$ denote the set of all the sequences in $C_j$ that have the symbol $a$ as the $(j + 1)$-st entry; thus $|P| \geq (1/k)|C_j|$. Let $Q$ denote the set obtained from $P$ by replacing the symbol $a$ in the $(j + 1)$-st entry of each sequence in $P$ by the new symbol $k$; put
\[ C_{j + 1} = C_j \cup Q. \]
Obviously, $C_{j + 1}$ satisfies (3) and (4); (2) holds as well, since
\[ (1 + 1/k)^{j + 1} |B| \leq ( 1+ 1/k) |C_j| \leq |C_{j + 1}|. \]
It remains to show that $C_{j + 1}$ is a good subset of $A(n,k + 1)$. Let $D \subset C_{j + 1}$ be a diagonal of $A(n,k + 1)$. We perform the following operation on the $i$-th column of the diagonal $D$, for each $i$, $1 \leq i \leq j + 1$. If the $i$-th column is running, or if it is a constant column where the constant is different from $k$, we do nothing. If the $i$-th column is constantly equal to $k$, then we replace it by a column constantly equal to the symbol $u_i$, where $u_i$ is the symbol guaranteed by condition (3) (for $C_{j + 1}$). Thus the new diagonal $D'$ so obtained, after all the first $j + 1$ columns have been operated on, is still contained in $C_{j + 1}$. Moreover, the first $k$ members of $D'$ are a diagonal of $A(n,k)$ and by (4) (for $C_{j + 1}$) are contained in $B$, contrary to assumption. Hence (1) is also satisfied for $C_{j + 1}$, and the induction step is completed. We thus obtain a good subset $C = C_n $ of $A(n, k + 1)$ with
\[ (1 + 1/k)^n |B| \leq |C|. \]
Now to show that the $k$-th column of $M$ is decreasing, let $B$ be a maximum cardinal good subset of $A(n + 1,k)$, and let $P$ be a subset of $B$ such that $|P| \geq (1/k)|B|$ and each sequence of $P$ has the same $(n + 1)$-st entry $a$. Let $Q$ be the subset of $A(n,k)$ obtained from $P$ by deleting the last symbol ($a$) from each sequence of $P$. Then clearly any diagonal of $A(n,k)$ in $Q$ gives rise (by reintroducing the last symbol $a$) to a diagonal of $A(n + 1,k )$ in $P \subset B$. Hence, $Q$ is a
good subset of $A(n,k)$, and
\[ d(n + 1, k) = k^{-(n + 1)}|B| \leq k^{-n} |P| = k^{-n}|Q| \leq d(n,k). \qedhere \]
\end{proof}
\begin{cor} Each column of the matrix $M$ is a convergent sequence, and the limit of the column limits exists.
\end{cor}
\begin{proof} By Proposition~\ref{prop: 1}, each column of $M$ is a monotone and bounded sequence; furthermore, the sequence of column limits is also monotone and bounded.
\end{proof}
We present a useful criterion for a subset of $A(n,k)$ to be good. In the following $d^{(i)}$ denotes $d^{(i)}_1 d^{(i)}_2 \cdots d^{(i)}_{n-1}$ and $d^{(i)}.x = d^{(i)}_1 d^{(i)}_2 \cdots d^{(i)}_{n-1} x$.
\begin{prop} \label{prop: 2}
Let $B \subset A(n,k)$ and let
\[ B_i = \{ a_1a_2 \cdots a_{n-1} \in A(n-1,k): a_1a_2 \cdots a_{n-1} i \in B\} \]
for $i = 0,1,\dots,k - 1$. Then $B$ is a good subset of $A(n,k)$ if and only if the following three conditions hold:
(i) Each $B_i$ is a good subset of $A(n-1,k)$.
(ii) $\bigcap_{i=0}^{k-1} B_i = \emptyset$.
(iii) If $D = \{d^{(0)}, d^{(1)}, \dots, d^{(k-1)}\}$ is a diagonal of $A(n-1,k)$, then, for some $i$, $d^{(i)} \notin B_i$.
\end{prop}
\begin{proof}
The set $B$ is a good subset of $A(n,k)$ if and only if it contains no diagonal of $A(n,k)$ in which the last column is constant (condition (i)), or the last column is the only running column (condition (ii)), or the last column and at least one other column are running (condition (iii) which states that
\[ D' = \{d^{(0)}.0, d^{(1)}.1, \dots, d^{(k-1)}.(k-1)\} \not\subset B). \]
The condition (ii) obtains a special meaning when $B$ is a good subset of $A(n,k)$ with the maximuum number $k^n - k^{n-1}$ of elements. Indeed, (ii) states that for each of the $k^{n-1}$ sequences $a_1a_2 \cdots a_{n-1}$ in $A(n-1,k)$ there exists a symbol $i$ such that
\[ a_1a_2 \cdots a_{n-1}i \notin B. \]
If $B$ contains all but $k^{n-1}$ elements of $A(n,k)$ then the above $i$ must be unique; let us denote it by $c(a_1a_2\cdots a_{n-1})$, that is, for each sequence $s \in A(n-1,k)$ $c(s)$ denotes that unique symbol $i$ for which $s \notin B_i$. We can view the function $c$ as an $(n-1)$-dimensional matrix with side $k$ and entries $0,1,2,\dots,k-1$. Conversely, to any such matrix this correspondence assigns a subset $B$ of $A(n,k)$ with $k^n- k^{n-1}$ elements.
\end{proof}
\begin{corn} \label{corn: 1}
The maximum value
\[ d(n,k) = 1 - 1/k \]
is attained if and only if there exists an $(n-1)$-dimensional matrix with side $k$ and entries $0,1,2,\dots,k-1$, such that for any diagonal $D = \{d^{(0)}, d^{(1)}, \dots, d^{(k-1)}\}$ of $A(n-1,k)$ the values
\[ c(d^{(0)}), c(d^{(1)}), \dots, c(d^{(k-1)}) \]
for a permutation of $0,1,\dots,k-1$ in which at least one
\[ i = c(d^{(i)}) \]
\end{corn}
\begin{proof}The maximum value is attained if and only if a good subset $B$ of $A(n,k)$ with $k^n - k^{n-1}$ elements can be found. Using the preceding remark we note that the condition (i) says that each symbol $0,1,\dots,k-1$ occurs among $c(d^{(0)}), c(d^{(1)}), \dots, c(d^{(k-1)})$, and the condition (iii) says that $i = c(d^{(i)})$ for some $i$.
\end{proof}
As an application we now determine the values in the first three rows of the matrix $M$.
\begin{corn} \label{corn: 2}
If $n = 1,2,3$, then
\[ d(n,k) = 1 - 1/k \]
for all $k$, with exactly one exception, $d(3,2) = 3/8$.
\end{corn}
\begin{proof} For $n = 1$, $B = A(1,k) \setminus \{0\}$ is a good subset of $A(1,k)$ with $k^1 - k^0 = k - 1$ elements; in fact, $c = 0$ can be regarded as a 0-dimensional matrix satisfying Corollary~\ref{corn: 1}. For $n = 2$, such a matrix is obtained by putting $c(i) = i$ for $i = 0,1,\dots,k-1$. For $n = 3$ the multiplication table of any idempotent quasigroup over $0,1,\dots,k-1$ satisfies our requirements. Such quasigroups exist, e.g.~\cite{gergely1974}, for $k \geq 3$. Of course, the case $k = 2$ is an exception, and the value of $d(3,2)$ follows from Sperner's Lemma.
\end{proof}
\begin{corn} \label{corn: 3}
$d(4,3) < 1 - 1/3$ and $d(4,4) < 1 - 1/4$.
\end{corn}
We omit the proofs of these inequalities; they are deduced rather routinely from Corollary~\ref{corn: 1}. Their interest lies mainly in comparison with Corollary~\ref{corn: 2} and the Corollary of Proposition~\ref{prop: 3}.
\begin{prop} \label{prop: 3}
If $\gcd(a,k) = 1$ for all $a = 1,2,\dots,n-1$, then $d(n,k) = 1 - 1/k$.
\end{prop}
\begin{proof} Let
\[ B = A(n,k) \setminus \{a_1a_2 \cdots a_n: a_1 + a_2 + \cdots + a_n \equiv 0 \textup{ (mod $k$)}\} \]
we add the symbols as ordinary integers). Then $|B| = k^n - k^{n-1}$, as for each $a_1a_2 \cdots a_{n-1} \in A(n-1,k)$ there is exactly one $a_n$ such that $a_1 + a_2 + \cdots + a_n \equiv 0$ (mod $k$). It remains to show that $B$ is a good subset of $A(n,k)$. Let $D$ be a diagonal of $A(n,k)$ having exactly $a$ running columns; let $b$ denote the sum of the $n - a$ symbols of the constant columns of $D$. Then the sum of the symbols in the $x$-th row of $D$ (the rows of $D$ are numbered from $0$ to $k-1$) is $ax + b$. The congruence
\[ ax + b \equiv 0 \textup{ (mod $k$)} \]
has a solution $x = 0$ when $a = n$ (i.e., $b = 0$), and a solution exists for $a = 1,2,\dots,n-1$, because $a,k$ are relatively prime. Hence $B$ contains no diagonal of $A(n,k)$.
\end{proof}
\begin{cor}
For all primes $p$,
\[ d(n,p) = 1 - 1/p \]
if $n \leq p$. In particular,
\[ d(p,p) = 1 - 1/p \]
fo all primes $p$.
\end{cor}
\section{Main Results} \label{sec: 3}
\begin{thm} \label{thm: 1}
For all $k \geq 2$ and all $m$, $d(mk,m) > (1 - 2/k)^{2m}$. If $p$ is prime, then $d(mp, p) \geq (1 - 1/p)^m$ for all $m$.
\end{thm}
\begin{proof} Let $k \geq 2$ and $m$ be given, and let $p$ be the largest prime less than or equal to $k$. According to Bertrand's Postulate (stating that for any positive integer $n$ there is a prime $q$ such that $n < q \leq 2n$) we have
\[ k < 2p. \]
Consider the number
\[ t = |\{a_1 a_2 \cdots a_p \in A(p,k): a_1+a_2 + \cdots + a_p \equiv 0 \textup{ (mod $p$)}\}| \]
and let $\theta = t/k^{p-1}$. For each $a_1a_2 \cdots a_{p-1} \in A(p-1,k)$ there is at least one but (as $k < 2p$) not more than two symbols $a_p$ with $a_1 + a_2 + \cdots + a_p \equiv 0$ (mod $p$). Therefore, $1 \leq \theta < 2$ and when $k$ itself is a prime, then $p = k$ and $\theta = 1$. For convenience of notation let $s = \lceil mk/p \rceil$ so that $mk = (s - 1)p + r$, where $1 \leq r \leq p$, and now think of sequences of length $mk $ on the symbols $0,1,\dots,k-1$ as being covered by $s - 1$ ``blocks" of length $p$ and a fixed block of length $r$. To be specific, for each sequence $a = a_1a_2 \cdots a_{mk}$ we define the blocks
\[ B_1(a) = a_1a_2 \cdots a_p, \quad B_2(a) = a_{p + 1} a_{p + 2} \cdots a_{2p}, \cdots \]
\[ B_{s - 1} (a) = a_{(s - 2)p + 1} a_{(s - 2)p + 2} \cdots a_{(s - 1)p}, \]
and
\[ B_s(a) = a_{(s - 1)p + 1} a_{(s - 1)p + 2} \cdots a_{mk}. \]
Note that the first $s - 1$ blocks are just the successive blocks of length $p$ from left to right, while the $s$-th block is the rightmost block of length $r$. We shall construct a good subset of $A(mk,k)$ with cardinal at least
\[ k^{mk}(1 - 2/k)^{2m}. \]
To this end, for each $j = 1,2,\dots,s$, let $S_j(a)$ denote the sum of all the sumbols in $B_j(a)$, and
\[ N_j = \{a \in A(mk,k): S_j(a) \equiv 0 \textup{ (mod $p$)}\}. \]
Finally, let
\[ B = A(mk,k) \setminus \bigcup_{j=1}^s N_j. \]
We shall first calculate $|B|$, then show that $B$ contains no diagonal. By the definition of $\theta$,
\[ |N_j| = \theta k^{p - 1} k^{mk - p} = \theta k^{mk - 1} \quad \textup{for $1 \leq j \leq s - 1$}. \]
Similarly, for $N_{j_1j_2 \cdots j_n} = N_{j_1} \cap N_{j_2} \cap \cdots \cap N_{j_n}$, $ 1\leq n \leq s- 1$ and
\[ 1 \leq j_1 < j_2 < \cdots < j_n \leq s- 1, \]
we have
\[ |N_{j_1j_2 \cdots j_n}| = \theta^n k^{mk - n}. \]
Let
\[ A = \bigcup_{j=1}^{s-1} N_j. \]
By inclusion-exclusion we obtain
\begin{align*} |A| &= \sum_{1 \leq i_1 \leq s- 1} |N_{i_1}| - \sum_{1 \leq i_1 < i_2 \leq s - 1} |N_{i_1i_2}| + \cdots \\
&= \sum_{n=1}^{s-1} (-1)^{n + 1} \sum_{1 \leq i_1 < \cdots < i_n \leq s - 1} |N_{i_1 i_2 \cdots i_n}| \\
&= -\sum_{n=1}^{s-1} (-1)^n \binom{s - 1}{n} \theta^n k^{mk - n} \\
&= k^{mk} - k^{mk}(1 - \theta/k)^{s - 1}. \end{align*}
Now
\[ \left| \bigcup_{j=1}^s N_j \right| = |A \cup N_s| = |A| + |N_s| - |A \cap N_s|. \]
Since
\[ |N_s| \leq 2k^{r-1} \]
and
\[ |A \cap N_s| \geq |A|.k^{-1}, \]
this gives
\begin{align*} \left| \bigcup_{j=1}^s N_j \right| &\leq k^{mk}(1 - (1 - \theta/k)^{s-1})(1 - 1/k) + 2k^{r - 1} \\
&\leq k^{mk} (1 - (1 - \theta/k)^{s-1})(1 - 1/k) + 2k^{k - 1}. \end{align*}
Thus
\[ |B| \geq k^{mk} \left[ (1 - \theta/k)^{s-1} . (1 - 1/k) + \left( \frac{1}{k} - \frac{2}{k^{mk - k + 1}} \right) \right]. \]
If $m >1$,
\begin{align*} |B| \geq k^{mk} [(1 - \theta/k)^{s-1}(1 - 1/k)] &> k^{mk} (1 - 2/k)^s \\
&\geq k^{mk}(1 - 2/k)^{2m}, \end{align*}
since $s = \lceil mk/p \rceil \leq 2m$. Note that if $k$ is prime, then $\theta = 1$ and $s = m$, so for $m> 1$ and $k$ prime we get $|B| \geq k^{mk}(1 - 1/p)^m$.
Now if $m = 1$ we have
\[ |B| \geq k^{mk}[(1 - \theta/k)^{s-1} . (1 - 1/k) - 1/k], \]
where $s = 1$ if $k$ is prime, and $s = 2$ if $k$ is not prime. If $k$ is prime then $d(k,k) = 1 - 1/k$ as we have shown earlier in the paper.
If $k$ is not prime then $s = 2$ and
\[ |B| > k^{mk} [(1 - 2/k)(1 - 1/k) - 1/k] > n^{mk}(1 - 2/k)^{2m}. \]
To show that $B$ is a good subset of $A(mk,k)$ we assume that a diagonal $D$ of $A(mk,k)$ is contained in $B$, and that some running column of $D$ is in the block $B_j$. Now we proceed in analogy to the proof of Proposition~\ref{prop: 3}: If $D$ has $a$ running columns \emph{in the block} $B_j$, and if $b$ is the sum of the symbols of the constant columns \emph{in the block} $B_j$, then $1 \leq a \leq p$ and the congruence
\[ ax + b \equiv 0 \textup{ (mod $p$)} \]
has a solution, $0 \leq x \leq p - 1 \leq k - 1$. In other words, the $x$-th row of $D$ belongs to $N_j$ and consequently is not in $B$.
Thus, $B$ is a good subset of $A(mk,k)$.
\end{proof}
Note that the Theorem tells us $d(mk,k) \to 1$ as $k \to \infty$ and the case $m = 1$ deals with the values (and their limit) on the main diagonal of $M$.
\begin{cor} If $\phi$ is any function of the set of positive integers into itself such that the sequence $\{\phi(k)/k\}$ is bounded by a constant, then
\[ d(\phi(k),k) \to 1 \textup{ as } k \to \infty; \]
hence the limit of the entries of $M$ along any path $\phi$ that lies above a non-vertical line is 1.
\end{cor}
\begin{proof} If $\phi(k) \leq mk$ for all $k$, then $d(\phi(k), k) \geq d(mk,k)$ by Proposition~\ref{prop: 1}, hence
\[ d(\phi(k), k) \to 1 \textup{ as } k \to \infty. \qedhere\]
\end{proof}
\section{Conclusions} \label{sec: 4}
It should be remarked that the principal interest of Theorem~\ref{thm: 1} is in allowing us to show that the limits of $M$ along all non-vertical lines are equal to 1. It should not be viewed as a significant estimate of $d(n,k)$ for a fixed $k$, that is, for the column convergence in $m$. In fact, when $k = 3$, Theorem~\ref{thm: 1} yields $d(3m,3) \geq (2/3)^m$, while by Proposition~\ref{prop: 2}, $d(3m,3) \geq d(3m,2) \geq K. 1/\sqrt{m}$ where $K$ is a fixed constant.
For small values of $n = 3m$ we obtained the following lower bounds for $d(3m,3)$ as compared to the values obtained from Theorem~\ref{thm: 1} and Proposition~\ref{prop: 2}.
\newpage
\begin{table}[h!]
\centering
\begin{tabular}[b] {|l | c | c| c| c| c| c| c| c| c| r|}
\hline
$n = 3m$ & 9 & 27 & 45 & 63 & 81 & 99 & 117 & 135 & 153 \\ \hline
$d(n,3) \geq$ & 0.576 & 0.448 & 0.404 & 0.379 & 0.362 & 0.348 & 0.337 & 0.327 & 0.319 \\ \hline
Prop.~\ref{prop: 2} & 0.246 & 0.149 & 0.117 & 0.099 & 0.088 & 0.080 & 0.073 & 0.068 & 0.064 \\ \hline
Theorem~\ref{thm: 1} & 0.296 & 0.026 & 0.002 & -- & -- & -- & -- & -- & $10^{-9}$ \\ \hline
\end{tabular}
\end{table}
The above lower bounds for $d(n,3)$ were obtained as follows: If $s \in A(n,3)$, we denote by $x_s,y_s,z_s$ the number of the various symbols (that is, 0,1,2) appearing in $s$, oredered so that $x_s \leq y_s \leq z_s$. Let $B$ be the set of all sequences $s \in A(n,3)$ which satisfy
(i) $x_s < y_s < z_s$,
(ii) $z_s - y_s = a_0 . 3^0 + \sum_{i=1}^l a_i . 3^i$ where $a_0 \in \{1,2\}$ and $a_i \in\{0,2\}$ for $i = 1,2,\dots,l$ with $a_l \ne 0$.
(iii) $y_s - x_s$ is even or $y_s - x_s \geq 3^t$.
Then $B$ is a good subset of $A(n,3)$ and it yields the above values.
Our results make the questions asked by Graham even more interesting and, in addition, they raise further questions. For example, we proved that in any row of $M$ the maximum value $1 - 1/k$ is attained for infinitely many $k$'s. Is it true that $d(n,k) = 1 - 1/k$ for all sufficiently large $k$? Is it true that $d(n,k) = 1 - 1/k$ implies $d(n,k + 1) = 1 - 1/(k + 1)$?
We wish to thank the referee for his helpful suggestions.
\bibliographystyle{amsplain}
\bibliography{tom-all}
\end{document}