%%%% THIS FILE IS AUTOMATICALLY GENERATED
%%%% DO NOT EDIT THIS FILE DIRECTLY,
%%%% ONLY EDIT THE SOURCE, tom-24/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{thrm}{Theorem}
\newtheorem{corl}{Corollary}
\newtheorem{lmma}{Lemma}
\newtheorem{prop}{Proposition}
\newtheorem{conj}{Conjecture}
\theoremstyle{remark}
\newtheorem*{rmrk}{Remark}
\title{The Ramsey property for collections of sequences not containing all arithmetic progressions}
\author{
Tom C. Brown\footnote{Department of Mathematics and Statistics, Simon Fraser University, Burnaby, British Columbia, V5A 1S6, Canada} and
Bruce M. Landman\footnote{Department of Mathematical Sciences, University of North Carolina at Greensboro, North Carolina 27412, USA}}
\maketitle
\begin{center}{\small {\bf Citation data:} T.C. {Brown} and Bruce~M. Landman, \emph{The {Ramsey} property for collections
of sequences not containing all arithmetic progressions}, Graphs and
Combinatorics \textbf{12} (1996), 149--161.}\bigskip\end{center}
\newcommand{\floor}[1]{{\left\lfloor{#1}\right\rfloor}}
\newcommand{\ceil}[1]{{\left\lceil{#1}\right\rceil}}
\newcommand{\A}{\ensuremath{\mathcal{A}}}
\newcommand{\B}{\ensuremath{\mathcal{B}}}
\begin{abstract}A family \B{} of sequences has the Ramsey property if for every positive
integer $k$, there exists a least positive integer $f_\B(k)$ such that for every
2-coloring of $\{1,2,\ldots,f_\B(k)\}$ there is a monochromatic $k$-term member
of \B. For fixed integers $m>1$ and $0\leq q 2$). This is not surprising, if we think of a
$q\Mod{m}$-sequence as an arithmetic progression, modulo $m$, with constant difference
$q$. Less expectedly, it turns out \cite{landman+long1994} that for all $m$ and
$q$, the family $\B_{q(m)}\cup\A_m$ does have the Ramsey property, and its
associated Ramsey function, which we denote by $f_{q(m),m}(k)$, satisfies
\[ f_{q(m),m}(k) = mk^2(1 + o(1)). \]
In this paper we consider several situations that are more general than those
dealt with in \cite{landman+long1994}. If $S = \{a_i \Mod{m_i}):
1\leq i\leq n\}$ is any set of congruence classes, we consider the family
of sequences that are $a_i\Mod{m_i}$-sequences for some $i$. For example,
if
\[ S = \{ 1\Mod4, 2\Mod3)\}, \]
then the sequences $\{1,2,11\}$ and $\{1,9,11\}$ belong to the family, while
$\{1,2,4\}$ and $\{1,9,10\}$ do not. We ask: (i) For which choices of $S$ will
the family of sequences have the Ramsey property? (ii) For such $S$, what is
the rate of growth of the associated Ramsey function $f_S(k)$?
In particular, we look at the family of arithmetic progressions modulo $m$, i.e.,
$\bigcup_{q=1}^{m-1}\B_{q(m)}$. It is clear that for almost all choices of $k$,
$m$ and $q$, the number of $k$-term arithmetic progressions modulo $m$ is
considerably greater than the number of sequences belonging to $\B_{q(m)}\cup
\A_m$. Yet, in Section \ref{s2} we show that the arithmetic progressions
modulo $m$ do not have the Ramsey property. As a corollary, if $T$ is a set
of positive integers, we are able to characterize those families $\B_{q(m)}
\cup \left(\bigcup_{t\in T} \A_t\right)$ which have the Ramsey property,
and we give upper bounds for the associated Ramsey functions $f_{q(m),T}$,
which generalize known results about $f_{q(m),m}$ from \cite{landman+long1994}.
In Section \ref{s3}, we first consider $|S| = 2$, and characterize those $S$
that give rise to the Ramsey property. We also give an upper bound for the
associated Ramsey function. We then look at the function $f_S$ for general
$S$. We give sufficient conditions for $f_S(k)$ to be defined for all $k$,
and show that for a large variety of $S$'s, these conditions are also
necessary. In Section \ref{s4} we consider a special case involving
partitions into $r\geq2$ classes, and obtain an upper bound for the
associated Ramsey function, where $S$ consists of $r$ congruences. Section
\ref{s5} includes some observations, based on computer output, concerning
the sharpness of the bounds.
We make use of the following additional notation and terminology.
If $i0$. For a fixed $t>0$, an
a.p. is called a \emph{$t$-a.p.} if $d=t$. If $m\geq2$ and $0\leq q\ceil{m/2}$.\label{t2}\end{thrm}
\begin{proof} Let $m\geq2$ and consider the following 2-coloring, $\chi$,
of the positive integers. For $1\leq x\leq \ceil{m/2}$ let $\chi(x)=0$,
and for $\ceil{m/2} + 1\leq x\leq m$ let $\chi(x) = 1$. When $x>m$, let
$\chi(x) = \chi(\bar{x})$, where $x\equiv\bar{x}\Mod{m}$ and $1\leq\bar{x}
\leq m$.
We will show that, with respect to $\chi$, the maximum size of a monochromatic
$q\Mod{m}$-sequence is bounded above by $\ceil{\frac{m}{2\gcd(q,m)}}\leq\ceil{
\frac{m}2}$ for each $q$, $1\leq q\leq m-1$. From this it follows immediately
that $f_S(k)=\infty$ if $k>\ceil{\frac{m}2}$.
Let $q$ be fixed ($1\leq q \leq m-1$), and let $d = \gcd(q,m)$, $s=m/d$. Now
regard $1,2,\ldots,m$ as the elements of the $m$-element cyclic group (where
$\bar{x} + \bar{y} = \overline{x+y}$), and let $H$ be the $s$-element cyclic
subgroup of $[1,m]$. By elementary group theory, we know that
\begin{equation}
H = \{\overline{q},\overline{2q},\ldots,\overline{sq}\} = \{d,2d,\ldots,sd\}.
\label{eq3}\end{equation}
Now let $x_1m/2$.
Now assume $cm\in T$. Note that if $\{x_1,\ldots,x_{(n-1)c+1}\}$ is an $m$-a.p.,
then $\{ x_{ic+1}:i=0,\ldots,n-1\}$ is a $cm$-a.p. Hence,
\[ f_{q(m),cm}(k,n) \leq f_{q(m),m}(k,(n-1)c+1). \]
Inequalities \eqref{eq4} and \eqref{eq5} follow from \eqref{eq1} and \eqref{eq2},
respectively.\end{proof}
\section{Using an Arbitrary Set of Congruence Classes\label{s3}}
We now direct our attention to the function $f_S$ for general $S$. The case
in which $|S|=1$ was considered in \cite{landman+long1994}. The authors showed
that if $S$ consists of the single congruence class $a\Mod{m}$, then as long
as $a\neq0$ and $k\geq3$, $f_S(k)=\infty$. They also showed that the only
case in which $|S|=1$ and $f_S(3)<\infty$ is if $q=0$, and that in fact,
for all $k\geq2$
\begin{equation} f_{0(m)}(k) = 2m(k-1)+1. \label{eq6}\end{equation}
We also see by Theorem \ref{t2}, that if $S = \{a_1\Mod{m},\ldots,a_r\Mod{m}:
a_i\neq0 \text{ for } 1\leq i\leq r\}$, then $f_S(k)=\infty$ whenever $k>m/2$.
Before dealing with the most general set $S$, we first consider the case in
which $|S|=2$. We now characterize those sets $S = \{a\Mod{m_1},b\Mod{m_2}:
a,b\neq0\}$ for which the corresponding collection of sequences has the
Ramsey property (if $a=0$ or $b=0$ we see by \eqref{eq6} that $f_S(k)$ does
exist for all $k$), and provide an upper bound for the corresponding Ramsey
function.
\begin{thrm}\label{t3}Let $m_1,m_2>1$, let $1\leq a3$. Let $d=\gcd(m_1,m_2)$ and $m=\lcm\{m_1,m_2\}$. Then
$f_{a(m_1),b(m_2)}(k)<\infty$ if and only if $d|a$ or $d|b$. Furthermore,
for all $k\geq3$, if $d|a$ or $d|b$, then $f_{a(m_1),b(m_2)}(k)d/2$, then $S = \{x_1,\ldots,
x_k\}$ is a semi $q\Mod{d}$-sequence in $[1,d]$ if and only if $S=\{x_k,
\ldots,x_1\}$ is a semi $(d-q)\Mod{d}$-sequence.
We now give a coloring of $[1,d]$ that avoids both 4-term monochromatic
semi $a\Mod{d}$-sequences and 4-term monochromatic semi $b\Mod{d}$-sequences.
Assuming $a**b$ or $x_3-x_1>b$). Thus, by definition of $\chi$, $\chi(x_r)
\neq \chi(x_{r+1})$.
\paragraph{Case II.} $a>b/2$.
\noindent Let $A_0 = [1,a]$, let $A_i = [(i-1)b+a+1,ib+a]$ for $i=1,\ldots,
h$ where $h=\floor{(d-a)/b}$, and let $A_{h+1} = [hb+1,d]$ ($A_{h+1}$
could be empty). Then each $A_i$ is monochromatic and the $A_i$'s alternate
in color. Assume $\{x,y,z\}$ is a monochromatic semi $a\Mod{d}$-sequence.
If $x$ and $y$ are in different $A_i$'s, then $y$ must be in $A_0$; but
then $\chi(z)\neq\chi(y)$. Therefore, we assume $x$ and $y$ are in the
same $A_{i_1}$. So $z\notin A_{i_1}$. Thus, $z\in A_0$, and hence $\chi(z+a)
\neq\chi(z)$. Thus there is no 4-term semi $a\Mod{d}$-sequence that is
monochromatic.
Now assume $d$ divides (say) $a$. We first consider the case in which
$\frac{m_2}{\gcd(m_2,b)}$ is even. Now $a\neq0$ implies $m_1\neq d$, so
that there exists a positive integer $c1$, $b>1$ and $\gcd(a,bc) = 1$.
Proposition \ref{p2} gives a very special class of sets $S$ for which the
converse of Theorem \ref{t4} fails. The next theorem gives sufficient
conditions on $S$ for $f_S(\vec{k})$ to be infinite for some $\vec{k}$,
which are satisfied by a large class of sets $S$. Note, in particular,
that Theorem \ref{t5} implies that the converse of Theorem \ref{t4}
does hold if $\gcd(a_i,m_i) = 1$ for all $i$.
\begin{thrm}\label{t5} Let $S=\{a_i\Mod{m_i}:1\leq i\leq n\}$. Let $e_i
=\gcd(a_i,m_i)$ for $1\leq i\leq n$, and $d_{ij}=\gcd\left(\frac{m_i}{e_i},
\frac{m_j}{e_j}\right)$ for $i\neq j$. Assume that for every pair $i\neq j$,
$d_{ij}$ divides neither $a_i$ nor $a_j$. Then $f_S(\vec{k}^*) = \infty$ where
$\vec{k}^* = (m_1/e_1,\ldots,m_n/e_n)$.\end{thrm}
\begin{proof} We first prove the result for the case in which $e_1=1$ for
all $i$. Let $m=\lcm\{m_1,\ldots,m_n\}$. By Lemma \ref{l2}, it suffices to
find a 2-coloring of $[1,m]$ that avoids $m_i$-term monochromatic semi
$a_i\Mod{m_i}$-sequences for all $i$.
Define the coloring $\chi:[1,m]\to\{0,1\}$ as follows:
\[ \chi(x) = \left\{\begin{array}{ll}
1&\text{if }x\equiv0\Mod{m_i}\text{ for some }i\\
0&\text{if }x\equiv{a_i}\Mod{m_i}\text{ for some }i\\
\text{arbitrary}&\text{otherwise}\end{array}\right. \]
Note that $\chi$ is well-defined on $[1,m]$ because if $i\neq j$ and $x\equiv0
\Mod{m_i}$, then (since $d_{ij}$ does not divide $a_j$) $x\not\equiv a_j\Mod{m_j}$.
Since $e_1=1$ for all $i$, any $m_i$-term semi $a_i\Mod{m_i}$-sequence
must contain an element from each congruence class modulo $m_i$. Hence,
no such sequence can be monochromatic under $\chi$. This proves the
theorem in case all $e_i=1$.
Now let the $e_i$ be arbitrary. Consider
\[ S' = \{a_i\Mod{m_i/e_i}:1\leq i\leq n\}. \]
Since $\gcd\left(a_i,\frac{m_i}{e_i}\right)=1$ and since $\gcd\left(\frac{a_i}{m_i},
\frac{a_j}{m_j}\right)$ divides neither $a_i$ nor $a_j$, we can apply the
case proven above (the case of all $e_i = 1$). Thus, there is a coloring
of the positive integers that avoids, for all $i$, $(m_i/e_i)$-term
monochromatic $a_i\Mod{m_i/e_i}$-sequences. Observing that every $a_i\Mod{m_i}$-sequence
is also an $a_i\Mod{m_i/e_i}$-sequence, the proof is complete.\end{proof}
\section{A Special Case\label{s4}}
Theorem \ref{t3} gives an upper bound, using 2 colors, for $f_{a(m_1),b(m_2)}(k)$,
when $d=\gcd(m_1,m_2)$ divides $a$ or $b$. If we use the stronger hypothesis that
$d$ divides both $a$ and $b$, we are able to give a much better upper bound.
In fact, we shall prove a result which deals with the more general case in
which there are $r$ colors and $|S| = r$. We first prove the following theorem.
\begin{thrm}\label{t6}Let $r\geq2$ and, for $1\leq i\leq r$, let $m_i>1$ and
$1\leq a_i**