%%%% THIS FILE IS AUTOMATICALLY GENERATED
%%%% DO NOT EDIT THIS FILE DIRECTLY,
%%%% ONLY EDIT THE SOURCE, tom-42/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{q}{Problem}
\theoremstyle{definition}
\newtheorem{defn}{Definition}
\newtheorem{fact}{Fact}
\newtheorem*{remark}{Remarks}
\newtheorem*{app}{Applications}
\newtheorem*{conj}{Conjecture}

\title{Quantitative Forms of a Theorem of Hilbert}
\author{T. C. Brown, P. Erd\H{o}s, F. R. K. Chung and R. L. Graham}
\date{}
\maketitle
\begin{center}{\small {\bf Citation data:} T.C. Brown, F.R.K. Chung, P.~Erd\H{o}s, and R.L. Graham, \emph{Quantitative
  forms of a theorem of {Hilbert}}, J. Combin. Theory Ser. A \textbf{38}
  (1985), 210--216.}\bigskip\end{center}

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

In an influential paper published in 1892, Hilbert proved the following result, which in some sense could be considered the first theorem in Ramsey theory. For positive integers $m,a$ and $a_k$, $1 \leq k \leq m$, define an $m$\emph{-cube} $Q_m = Q_m(a,a_1,\dots,a_m)$ to be the set
\[ \left\{ a + \sum_{k=1}^m \varepsilon_ka_k : \varepsilon_k = 0 \textup{ or } 1, 1 \leq k \leq m \right\}. \]

\begin{lemma} \emph{(Hilbert~\cite{hilbert1892})}. For any positive integers $m$ and $r$ there exists a least integer $h(m,r)$ such that if the set $\{1,2,\dots,h(m,r)\}$ is arbitrarily partitioned into $r$ classes $C_k$, $1 \leq k \leq r$, some $C_i$ must contain an $m$-cube.
\end{lemma}

Hilbert needed this lemma in connection with certain results on the irreducibility of rational functions and, as far as is known, never pursued the combinatorial directions to which it pointed. Others did, however, beginning with Schur, who in 1916 showed that for any $r$, there is an $s(r)$ so that in any partition of $\{1,2,\dots,s(r)\}$ into $r$ classes, some class contains a \emph{projective} $2$-cube, i.e., $Q_2^*(a_1,a_2) = Q_2(a,a_1,a_2) - \{0\}$ with $a = 0$. (This combinatorial result actually arose in Schur's investigations~\cite{schur1916} of a modular version of Fermat's conjecture.) This was later extended by Rado~\cite{rado1933} (who was Schur's student) who (implicitly) proved that any partition of a sufficiently long interval of integers into $r$ classes must have at least one class which contains a projective $m$-cube. This was also proved independently later by Folkman (see~\cite{graham+rothschild1971-1}) and Sanders~\cite{sanders1969}. Finally, in 1974, Hindman~\cite{hindman1974} proved the much stronger result that in any partition of all the positive integers into finitely many classes, some class must contain an \emph{infinite} projective cube, i.e., for positive integers $a_1,a_2,\dots$ a set 
\[ \left\{ \sum_{k=1}^\infty \varepsilon_k a_k : \varepsilon_k = 0 \textup{ or } 1 \textup{ with } 0 < \sum_{k=1}^\infty \varepsilon_k < \infty \right\}. \]
In this note we investigate the function $h(m,r)$ and several related ones. In particular we derive rather sharp bounds on them for the (first interesting) case $m = 2$. We shoul point out here that in contrast to the rapidly growing functions associated with projective $m$-cubes (e.g., $s(r)$ is known~\cite{chung+grinstead1983,frederickson1979,schur1916} to satisfy $c \cdot 315^{r/5} < s(r) \leq [er!]$, for a suitable $c > 0$), for any fixed $m$, $h(m,r)$ is bounded by a polynomial in $r$. 

\vspace{12pt}
\emph{2-cubes}

To begin with, an easy calculation shows that a set $A \subset \mathbb{Z}^+$ (the positive integers) contains no 2-cube if and only if 
\begin{equation} a,b,c,d \in A, a + b = c + d \Rightarrow \{a,b\} = \{c,d\}, \label{eq: 1} \end{equation} 
i.e., all the pair sums $x + y, x,y \in A$ are distinct. Such sets $A$ (often called $B_2$-sets) have been extensively studied in the literature (e.g., see~\cite{halberstam+roth1966}). In particular, it is known~\cite{halberstam+roth1966} that if $A \subseteq [n] := \{1,2,\dots,n\}$ satisfies~(\ref{eq: 1}) then 
\begin{equation} |A| \leq (1 + o(1)) \sqrt{n}. \label{eq: 2} \end{equation}
Thus, if we partition $[n]$ into $B_2$-sets, say
\begin{equation} [n] = \bigcup_{k=1}^t A_k \label{eq: 3} \end{equation}
then by~(\ref{eq: 2}) we must have
\begin{equation} t \geq \frac{n}{\max_k |A_k|} \geq (1 + o(1)) \sqrt{n}. \label{eq: 4} \end{equation}
This implies 
\begin{equation} h(2,r) \leq (1 + o(1))r^2. \label{eq: 5} \end{equation}
Our next goal is to establish the reverse inequality in~(\ref{eq: 5}). It is well known (see~\cite{storer1967}) that for any prime $p$ there exists a simple difference set $D = \{d_0,d_1,\dots,d_p\}$ (mod $p^2 + p + 1$). That is, any nonzero $t \in \mathbb{Z}_{p^2 + p + 1}$ has a \emph{unique} representation as $t \equiv d_i - d_j$ (mod $p^2 + p + 1$) and consequently, all $d_i - d_j$, $i \ne j$, are distinct. Define
\[ D_j := D - d_j = \{d_i - d_j: 0 \leq i \leq p\} \textup{ (mod $p^2 + p + 1$)}, \]
where we have translated all the elements of $D_j$ so that they lie between $0$ and $p^2 + p$. We claim that $D_j$ satisfies~(\ref{eq: 1}). For if not then for some $i_1,i_2,i_3,i_4$ with $\{i_1,i_2\} \ne \{i_3,i_4\}$,
\[ (d_{i_1} - d_j) + (d_{i_2} - d_j) \equiv (d_{i_3} - d_j) - (d_{i_4} - d_j) \textup{ (mod $p^2 + p + 1$)}, \]
i.e.,
\[ d_{i_1} - d_{i_3} \equiv d_{i_4} - d_{i_2} \textup{ (mod $p^2 + p + 1$)} \]
which by the definition of a simple difference set implies $i_1 = i_4, i_3 = i_2$. However, this implies $\{i_1,i_2\} = \{i_3,i_4\}$ which is a contradiction. Furthermore, observe that since any $t \in \mathbb{Z}_{p^2 + p + 1}$ can be written as $t \equiv d_i - d_j$ (mod $p^2 + p + 1$) then the $D_j$, $0 \leq j \leq p$, \emph{cover} $[p^2 + p]$. Thus, $[p^2 + p]$ can be partitioned into $p + 1$ $B_2$-sets and so,
\begin{equation} h(2, p + 1) \geq p^2 + p + 1. \label{eq: 6} \end{equation}
Since the ratio between consectutive primes tends to $1$ we then have 
\begin{equation} h(2,r) \geq (1 + o(1)) r^2. \label{eq: 7} \end{equation}
Combining~(\ref{eq: 5}) and~(\ref{eq: 7}) we finally obtain:

\begin{thm} \label{thm: 1}
\begin{equation} h(2,r) = (1 + o(1))r^2. \label{eq: 8} \end{equation} 
\end{thm}

We should point out that this result is closely related to the value of the Ramsey number for 4-cycles (see~\cite{graham1981}).

\vspace{12pt}
\emph{Deleted 2-cubes}

It is natural to expect that if the conditions on the forbidden subsets are relaxed then the number of clases in a valid partition must increase. As an example of this, we now consider what could be called \emph{deleted} 2-cubes. By this we just mean sets of the form $\{a + x, a + y, a + x+ y\}$ for some $a \geq 0$ and $x,y \geq 1$, i.e., an ordinary 2-cube with the point corresponding to $\varepsilon_1 = \varepsilon_2 = 0$ deleted. It turns out it makes a rather substantial difference whether we allow $x = y$ or not. Define $\bar{h}(2,r)$ to be the least integer $\bar{h}$ such that in any partition of $[\bar{h}]$ into $r$ classes, some class contains a set $\bar{Q}(a,x,y) = \{a + x,a + y, a + x + y\}$ for some $a \geq 0$ and $ 1\leq x \leq y$. Similarly define $h^*(2,r)$ in the same way except that now we require $1 \leq x < y$.

\begin{thm} \label{thm: 2}

(i) $\bar{h}(2,r) = 2r$;

(ii) $h^*(2,r) \geq (1 + o(1)) \frac{11}{3}r$;

(iii) $h^*(2,r) \leq (1 + o(1)) \frac{26}{7} r$.
\end{thm}

\begin{proof}
The proof of (i) is straightforward. For any partition of $[2r]$ into $r$ classes, some class $C$ must contain integers satisfying $r \leq u < v \leq 2r$. Since $a:= 2u - v \geq 0$ then the set $\bar{Q}(a,v-u,v-u)$ belongs to $C$, and so, $\bar{h}(2,r) \leq 2r$. On the other hand, the partition $[2r - 1] = \bigcup_{k=1}^{r - 1} \{k, k + r\} \cup \{r\}$ shows that $\bar{h}(2,r) > 2r - 1$.

\begin{proof}[Proof of (ii)]
It is easy to check that a set $A \subseteq \mathbb{Z}^+$ contains no set of the form $\{a + x, a+ y, a + x + y\}$ with $a \geq 0$, and $1 \leq x < y$ if and only if 
\begin{equation} u,v,w \in A \textup{ with } u < v< w \Rightarrow u + v < w. \label{eq: 9} \end{equation} 
We want to show that it is always possible to partition $[11n]$ into $3n + o(n)$ such sets. To do this, we describe a specific construction. Define $A(k), B(k),$ and $C(k), 1 \leq k \leq n$, by 
\begin{align*} A(k) &= \{2n - 2k, 2n + k, 4n - k + 1, 7n - k + 1, 11n - 2k + 3\} \\
B(k) &= \{2n - 2k - 1, 7n + k, 9n - k\} \\
C(k) &= \{5n - k, 6n - k, 11n - 2k + 2\}. \end{align*}
It is easy to check that for $1 \leq k < n$, each of $A(k), B(k)$, and $C(k)$ satisfies~(\ref{eq: 9}) and furthermore, with the exception of a bounded number of elements, their union covers $[11n]$. Thus
\[ h^*(2,3n) \geq 11n + o(1) \]
and consequently (ii) holds.
\end{proof}

\begin{proof}[Proof of (iii)]
Suppose we have a partition of $[\frac{11}{39}, \dots, n]$ into classes, each of which satisfies~(\ref{eq: 9}). We will show that there must be at least $\frac{7}{26} n + o(n)$ classes, which in turn, will establish (iii). We distinguish three types of classes in the partition, depending on the number of elements in the class. We have 
\begin{align*} A_i &= \{a_1^{(i)} < a_2^{(i)} < a_3^{(i)} < a_4^{(i)} \}, &&1 \leq i \leq an, \\
B_i &= \{ b_1^{(i)} < b_2^{(i)} < b_3^{(i)} \}, &&1 \leq i \leq bn, \\
C_i &= \{ c_1^{(i)} < c_2^{(i)} \}, &&1 \leq i \leq cn.
\end{align*}
Note that since all elements are greater than $n/5$ and each class satisfies~(\ref{eq: 9}) then no class can have 5 or more elements. Also, any two sets each with a single element can be combined without loss of generality to form a $C_i$. By hypothesis,
\begin{align} 
a_1^{(i)} + a_2^{(i)} &< a_3^{(i)} \notag \\
a_2^{(i)} + a_3^{(i)} &< a_4^{(i)} \label{eq: 10} \\
b_1^{(i)} + b_2^{(i)} &< b_3^{(i)}. \notag \end{align}
Summing these inequalities we obtain
\begin{equation} \sum_{i=1}^{an} (a_1^{(i)} + 2a_2^{(i)}) + \sum_{j=1}^{bn} (b_1^{(j)} + b_2^{(j)}) < \sum_{i=1}^{an} a_4^{(i)} + \sum_{j=1}^{bn} b_3^{(j)}. \label{eq: 11} \end{equation}

Also, by counting the total numbr of elements we have 
\begin{equation} 4a + 3b + 2c \leq \frac{28}{39}. \label{eq: 12} \end{equation}

We want to \emph{minimize} the number of classes $w = (a + b + c)n$.

To begin with, it is not difficult to see that the least value the LHS of~(\ref{eq: 11}) can assume is obtained by taking the $a_2^{(i)}$ as small as possible (because of the coefficient 2). Basically, this means that $[\frac{11}{39}n, \dots,n]$ is partitioned as 
\[ (a_1^{(1)}a_2^{(1)}a_1^{(2)}a_2^{(2)}a_1^{(3)}a_2^{(3)}\cdots b_1^{(1)}b_2^{(1)}b_1^{(2)}b_2^{(2)}]. \]
Thus
\begin{align}
\sum_{i=1}^{an} (&a_1^{(i)} + 2a_2^{(i)}) + \sum_{j=1}^{bn} (b_1^{(j)} + b_2^{(j)}) \notag \\
&\geq \sum_{k=1}^{(2a + 2b)n} (\frac{11}{39} n + k) + \sum_{k=1}^{an} (\frac{11}{39} n + 2k) \notag \\
&= n^2((3a + 2b)\cdot \frac{11}{39} + 2(a + b)^2 + a^2) + o(n^2). \label{eq: 13} \end{align}
On the other hand, the RHS of~(\ref{eq: 11}) is bounded above by 
\begin{align} \sum_{i=1}^{an} a_4^{(i)} + \sum_{j=1}^{bn} b_3^{(j)} &\leq \sum_{k=1}^{(a + b)n} (n - k + 1) \notag \\
&= n^2 (a + b - \frac{1}{2}(a + b)^2) + o(n^2). \label{eq: 14} \end{align}
Combining~(\ref{eq: 11}),~(\ref{eq: 13}), and~(\ref{eq: 14}) we obtain
\[ \frac{11}{39} (3a + 2b) + 2(a + b)^2 + a^2 \leq a + b - \frac{1}{2}(a + b)^2 + o(1) \]
which simplifies to
\begin{equation} 
\frac{7}{2} a^2 + 5ab + \frac{5}{2}b^2 \leq \frac{6}{39} + \frac{17}{39} b. \label{eq: 15} \end{equation}
It is now straightforward to solve this quadratic programming problem (subject, of course, to the conditions that $ a,b,c, \geq 0$). The result is that the minimum value of $a + b + c$ is $\frac{7}{26}$, which is attained when $a = \frac{1}{39} b = \frac{5}{39}, c = \frac{3}{26}$. This proves (iii).
\end{proof} 
\end{proof}

With more complicated arguments, it is possible to increase the bound $\frac{7}{26}n$ somewhat, but at present we are unable to close the gap betwen the lower bound and the upper bound of $\frac{3}{11}n$ (which may well be the ``truth").

\vspace{12pt} 
\emph{Larger values of $n$}

Relatively little is known for $h(m,r)$ with $m > 2$. An easy induction argument (used in~\cite{hilbert1892}) shows that 
\[ h(m,r) \leq (r + 1)^{F_{2m}}, \]
where $F_k$ denotes the $k$th Fibonacci number, i.e., $F_0 = 0$, $F_1 = 1$, and $F_{k + 2} = F_{k + 1} + F_{k}$. Thus 
\[ h(m,r) < r^{c^m} \]
for a suitable $c$.

In fact, a stronger ``density" result actually holds here. In~\cite{szemeredi1975} (see also~\cite{graham+rothschild+spencer1980}), Szemer\'{e}di shows that if $A \subseteq [M]$ has 
\[ |A| > M/r \]
and 
\[ M > (3r)^{e^m} \]
then $A$ contains an $m$-cube.

We do not at present have anything interesting to state concerning lower bounds for $h(m,r)$ (although bounds of the form $r^{cm}$ are easy to obtain).

For projective $m$-cubes, Taylor~\cite{taylor1981} has recently shown that if the set $[N]$ is partitioned into $r$ classes then some class contains a projective $m$-cube provided 
\[ N \geq \overbrace{2^{3^{r^{\cdot^{\cdot^{r^3}}}}}}^{2r(m - 1)} \quad \textup{for }m,r \geq 2. \]
While this bound may appear large, it was actually a tremendous improvement over previous bounds (being primitive recursive, for example).



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