\documentclass[12pt]{article} \textwidth= 6.5in \textheight= 9.0in \topmargin = -20pt \evensidemargin=0pt \oddsidemargin=0pt \headsep=25pt \parskip=10pt \font\smallit=cmti10 \font\smalltt=cmtt10 \font\smallrm=cmr9 \usepackage{latexsym,amssymb} \newtheorem{theorem}{Theorem} \newtheorem{lemma}{Lemma} \newtheorem{construction}{Construction} \newtheorem{proposition}{Proposition} \newtheorem{conjecture}{Conjecture} \newtheorem{corollary}{Corollary} \newtheorem{question}{Question} \newtheorem{inequality}{Inequality} \newtheorem{problem}{Problem} \newcommand{\definition} {\medskip\noindent {\bf Definition:}\hspace{0em}} \newcommand{\qindent}{\hspace{0em}} \newcommand{\rank} {\textrm{rank}} \newcommand{\dor} {\textrm{dor}} \newcommand{\remark} {\medskip\noindent {\bf Remark.\hspace{0em}}} \newenvironment{proof} {\medskip\noindent{\it Proof.}\hspace{1mm}} {\hfill$\Box$\medskip} \newenvironment{proofof}[1] {\medskip\noindent{\it Proof of #1.}\hspace{1mm}} {\hfill$\Box$\medskip} \def\rados{Radoi\v ci\'c} \def\qed{\hfill $\Box$} \begin{document} \vspace*{-60pt} \centerline{\smalltt INTEGERS: \smallrm ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 5(1) (2005), \#A32} \begin{center} \uppercase{\bf On the degree of regularity of generalized van der Waerden triples} \vskip 20pt {\bf Jacob Fox}\\ {\smallit Massachusetts Institute of Technology, Cambridge, MA 02139, USA}\\ {\tt licht@mit.edu}\\ \vskip 10pt {\bf Rado\v{s} \rados}\\ {\smallit Department of Mathematics, Rutgers, The State University of New Jersey, Piscataway, NJ 08854, USA}\\ {\tt rados@math.rutgers.edu}\\ \end{center} \vskip 30pt \centerline{\smallit Received: 6/9/05, Accepted: 11/28/05, Published: 12/13/05} \vskip 30pt \centerline{\bf Abstract} \noindent Let $a$ and $b$ be positive integers such that $a \le b$ and $(a,b) \not =(1,1)$. We prove that there exists a $6$-coloring of the positive integers that does not contain a monochromatic $(a, b)$-triple, that is, a triple $(x,y,z)$ of positive integers such that $y=ax+d$ and $z=bx+2d$ for some positive integer $d$. This confirms a conjecture of Landman and Robertson. \pagestyle{myheadings} \markright{\smalltt INTEGERS: \smallrm ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 5(1) (2005), \#A32\hfill} \thispagestyle{empty} \baselineskip=15pt \vskip 30pt % main text \section*{\normalsize 1. Introduction} \label{intro} In 1916, Schur \cite{Sc} proved that for every finite coloring of the positive integers there is a monochromatic solution to $x+y=z$. In 1927, van der Waerden \cite{Wa} proved that every finite coloring of the positive integers contains arbitrarily long monochromatic arithmetic progressions. Rado's 1933 thesis \cite{Ra} was a seminal work in Ramsey theory, generalizing the earlier theorems of Schur and van der Waerden. Rado called a linear homogenous equation $a_1x_1+ \ldots + a_nx_n = 0$ ($a_i$'s are nonzero integers) $r$-{\it regular} if every $r$-coloring of $\mathbb{N}$ contains a monochromatic solution to that equation. An equation is {\it regular} if it is $r$-regular for all positive integers $r$. Rado's theorem for a linear homogeneous equation states that an equation is regular if and only if a non-empty subset of $a_i$'s sums to $0$. Rado also made a conjecture \cite{Ra} that further differentiates between those linear homogeneous equations that are regular and those that are not. %\vspace*{0.2in} \begin{conjecture} (Rado's Boundedness Conjecture, 1933) For every positive integer $n$, there exists an integer $k := k(n)$ such that every linear homogeneous equation $a_1x_1+\ldots+a_nx_n=0$ that is $k$-regular must be regular as well. \end{conjecture} %\vspace*{0.2in} This outstanding conjecture has remained open except in the trivial cases ($n=1,2$) until recently, when the first author and Kleitman settled the first nontrivial case $n=3$ \cite{FoKl}, \cite{HiLeSt}. They proved that $k(3)\le 24$. Van der Waerden's theorem has been strengthened and generalized in numerous other ways \cite{BeLi}, \cite{BrGrLa}, \cite{Fu}, \cite{Go}, \cite{GrRoSp}, \cite{LaRo1}, \cite{Sz}. In this note, we consider one of the generalizations, proposed by Landman and Robertson in \cite{LaRo}. Let $a$ and $b$ be positive integers such that $a\le b$. A triple $(x,y,z)$ of positive integers is called an $(a,b)$-triple if there exists a positive integer $d$ such that $y=ax+d$ and $z=bx+2d$. The {\it degree of regularity} of an $(a,b)$-triple, denoted by $\mbox{dor}(a,b)$, is the largest positive integer $r$, if it exists, such that for every $r$-coloring of the positive integers there is a monochromatic $(a,b)$-triple. If no such $r$ exists, that is, for every finite coloring of the positive integers there is a monochromatic $(a,b)$-triple, then set $\mbox{dor}(a,b)=\infty$. Note that van der Waerden's theorem for $3$-term arithmetic progressions is equivalent to $\mbox{dor}(1,1)=\infty$. Landman and Robertson proved that $\mbox{dor}(a, b) = 1$ if and only if $b = 2a$. They also showed that $\mbox{dor}(a,2a-1)=2$ for $a \geq 2$. For small values of $a$ and $b$, they provide few additional results: $$\mbox{dor}(1, 3) \le 3, \mbox{ dor}(2, 2)\le 5, \mbox{ dor}(2, 5)\le 3, \mbox{ dor}(2, 6)\le 3,$$ $$\mbox{dor}(3, 3)\le 5, \mbox{ dor}(3, 4)\le 5, \mbox{ dor}(3, 8)\le 3, \mbox{ dor}(3, 9)\le 3.$$ Finally, they conjectured that if $(a,b) \not =(1,1)$, then $dor(a,b)$ is finite \cite{LaRo}, \cite{LaRo1}. %some of which improve the previously mentioned bound: %They also showed that if $b \ge (2\sqrt{2} -1)a + 2 - 2\sqrt{2}$, %then $\mbox{dor}(a, b) \le \lceil 2\log_2{\lceil b/a \rceil} \rceil$. %For example, this bound yields $dor(a,2a-1)=2$ for $a \geq 2$. We confirm and further strengthen their conjecture. %\vspace*{0.2in} \begin{theorem} \label{thm} If $(a,b) \not =(1,1)$, then $\mbox{dor}(a,b) < 6$. \end{theorem} %\vspace*{0.2in} Our proof that $\mbox{dor}(a,b)$ is finite uses Rado's theorem for a homogenous linear equation. Proving a specific upper bound of $6$, regardless of parameters $a$ and $b$, relies on the above mentioned proof of Fox and Kleitman \cite{FoKl}. \section*{\normalsize 2. Proof of Theorem~\ref{thm}} First, notice that if $(x,y,z)$ is an $(a,b)$-triple, then $(x,y,z)$ satisfies the equation $$-(b-2a)x-2y+z=0.$$ By Rado's theorem \cite{Ra}, this equation is regular if and only if $b\in \{2a-2, 2a-1, 2a+1\}$. Therefore, if $b-2a \not \in \{-2,-1,1\}$, then $\mbox{dor}(a,b)$ is finite. Moreover, since $k(3) \le 24$ \cite{FoKl}, if $b-2a \not \in \{-2,-1,2\}$, then $\mbox{dor}(a,b) \le 23$. As mentioned in the introduction, Landman and Robertson \cite{LaRo} proved that $\mbox{dor}(a,2a-1)=2$ for $a \geq 2$. For the remaining cases, we use Lemma \ref{lm}, which is stated and proved next. \begin{lemma} \label{lm} Let $\alpha$ and $\beta$ be real numbers such that $1 < \alpha < \beta$. Set $r=\lceil \log_{\alpha} \beta \rceil$. Then every $r$-coloring of the positive integers contains integers $x$ and $y$ of the same color with $\alpha x \leq y \leq \beta x$. Moreover, there is an $(r+1)$-coloring of the positive integers that contains no integers $x$ and $y$ of the same color with $\alpha x \leq y \leq \beta x$. \end{lemma} \begin{proof} Consider a coloring of $\mathbb{N}$ without $x$ and $y$ of the same color with $\alpha x \leq y \leq \beta x$. Since $r=\lceil \log_{\alpha} \beta \rceil$, then $\alpha^{r-1}<\beta$. Let $x_1 > \sum_{k=0}^{r-2}\alpha^{k}/(\beta-\alpha^{r-1})$ be a positive integer. For $i > 1$, set $x_{i+1}= \lceil \alpha x_i \rceil$. We have $\alpha x_i \leq x_{i+1}<\alpha x_i+1$. Repeatedly using the inequality $x_{i+1}<\alpha x_i+1$, we obtain $x_r < \alpha^{r-1}x_1+\sum_{k=0}^{r-2}\alpha^k$. Since we appropriately chose $x_1$, the last inequality yields $x_r < \beta x_1$. Hence, $\alpha x_i \leq x_j \leq \beta x_i$ for $1 \leq i x$, we have $y > \alpha^r x \ge \beta x$. Therefore, this $(r+1)$-coloring of the integers has no monochromatic $x$ and $y$ such that $\alpha x \leq y \leq \beta x$. \end{proof} Now, we continue with the proof of Theorem~\ref{thm}. We have two cases. \noindent{{\bf Case 1.}} $b=2a+1$. In this case, we have $y=ax+d$ and $z=(2a+1)x+2d$. Therefore, $2y2$, then $y=ax+d$ and $z=(2a-2)x+2d$. So, $(\frac{2a-2}{a})y \sqrt{2}$ when $a>3$. Therefore, $2\leq \mbox{dor}(a,2a-2) \leq 3$ for $a=3$ and $\mbox{dor}(a,2a-2)=2$ for $a>3$. At this stage, we have $\mbox{dor}(a,b) < 24$, whenever $(a,b) \not =(1,1)$. Next, we improve the upper bound using some sophisticated tools from the paper of Fox and Kleitman \cite{FoKl}. For the sake of completeness and clarity, we repeat some of their analysis that applies in our context. We need the following bit of notation. \begin{definition} Let $p$ be a prime number. For every integer $n$, let $v_p(n)$ denote the largest power of $p$ that divides $n$. If $n = 0$, let $v_p(n) = +\infty$. \end{definition} Notice that $v_p(m_1m_2) = v_p(m_1) + v_p(m_2)$ for every prime $p$, and integers $m_1$ and $m_2$. The following straightforward lemma (Lemma 3 in \cite{FoKl}) gives basic properties of the function $v_p$, which we will repeatedly use. \begin{lemma} \label{v_p} If $m_1$, $m_2$, $m_3$ are integers with $v_p(m_1) \le v_p(m_2) \le v_p(m_3)$ and $v_p(m_1) < v_p(m_1 + m_2 + m_3)$, then $v_p(m_1) = v_p(m_2)$. Furthermore, if $v_p(m_3) < v_p(m_1 + m_2 + m_3)$, then also $v_p(m_1 + m_2) = v_p(m_3)$. \end{lemma} Recall that if $(x,y,z)$ is an $(a,b)$-triple, then $(x,y,z)$ satisfies the equation $(b-2a)x+2y-z=0$. Let $t_x = b-2a$, $t_y = 2$, and $t_z = -1$ denote the coefficients of $x$, $y$, and $z$ in this equation, respectively. We have three cases to consider, depending on $t_x$. \noindent{{\bf Case A.}} $t_x$ is a multiple of $4$. Clearly, we have $v_2(t_x) > v_2(t_y) = 1 > v_2(t_z) = 0$. Let $S = \{v_2(t_x), v_2(t_y), v_2(t_x)-v_2(t_y)\}$, and let $\Gamma(S)$ be the undirected Cayley graph of the group $(\mathbb{Z}, +)$ with generators being the elements of $S$. Since every vertex of $\Gamma(S)$ has degree $2|S|$, there exists a proper (greedy) $(|S|+1)$-coloring $\chi '$ of its vertices. This result is ``folklore'' and we refer the reader to Lemma 2 in \cite{FoKl} for details. Now, define $\chi(n) = \chi '(v_2(n))$, for every $n\in \mathbb{N}$. We claim that in the 4-coloring $\chi$ of $\mathbb{N}$ there are no $x$, $y$, and $z$, all of the same color and $v_2(t_xx+t_yy+t_zz) > \mbox{min}\{v_2(t_xx), v_2(t_yy), v_2(t_zz)\}$. Indeed, otherwise (by Lemma \ref{v_p}) we have $v_2(t_xx) = v_2(t_yy)$; or $v_2(t_xx) = v_2(t_zz)$; or $v_2(t_yy) = v_2(t_zz)$. This implies $v_2(y) - v_2(x) = v_2(t_x)-v_2(t_y)$; or $v_2(z) - v_2(x) = v_2(t_x)$; or $v_2(z) - v_2(y) = v_2(t_y)$. However, this contradicts that $\chi '$ is a proper coloring of $\Gamma(S)$ and $v_2(x)$, $v_2(y)$, and $v_2(z)$ are all of the same color. Since $v_2(0) = +\infty$, by definition, and since there are no $x$, $y$, $z$, all of the same color and $v_2(t_xx+t_yy+t_zz) > \mbox{min}\{v_2(t_xx), v_2(t_yy), v_2(t_zz)\}$, then, in particular, there are no monochromatic solutions to $t_xx+t_yy+t_zz = 0$ (i.e. $(b-2a)x+2y-z=0$) in $\chi$. Case A is equivalent to Lemma 4 (with $p = 2$) in \cite{FoKl}. \noindent{{\bf Case B.}} $t_x$ has an odd prime factor $p$.\footnote{ Note that Cases A and B overlap. However, it is only important that Cases A, B, and C cover all the possibilities.} In this case we have $v_p(t_x) > v_p(t_y) = v_p(t_z) = 0$. Let $d = v_p(t_x)$. We construct a $6$-coloring $\chi$ that is a product of a $2$-coloring $\chi_1$ and a 3-coloring $\chi_2$. For $n\in \mathbb{N}$ define $\chi_1(n) \equiv \lfloor \frac{v_p(n)}{d} \rfloor \pmod{2}$. The coloring $\chi_1(n)$ colors intervals of $v_p$ values of length $d$, open on one side, periodically in $2$ colors with period $2$. Let $\Gamma$ be the undirected Cayley graph on $\mathbb{Z}_p \setminus \{0\}$ such that $(u, v)$ is an edge of $\Gamma$ if and only if $u - 2v \equiv 0 \pmod{p}$ or $2u-v \equiv 0 \pmod{p}$. Since every vertex of $\Gamma$ has degree 2, there exists a proper $3$-coloring $\chi_2': V(\Gamma)\rightarrow \{0, 1, 2\}$. For $n\in \mathbb{N}$ define $\chi_2(n) = \chi_2'(m \mbox{ mod } p)$, where $n = mp^{v_p(n)}$. Finally, for $n\in \mathbb{N}$ define $\chi(n) = (\chi_1(n), \chi_2(n))$. We claim that in the 6-coloring $\chi$ of $\mathbb{N}$ there are no $x$, $y$, and $z$, all of the same color and $v_p(t_xx+t_yy+t_zz) > \mbox{max}\{v_p(t_xx), v_p(t_yy), v_p(t_zz)\}$. Indeed, otherwise (by Lemma \ref{v_p}) we have $v_p(t_xx) = v_p(t_yy)\le v_p(t_zz)$; or $v_p(t_xx) = v_p(t_zz)\le v_p(t_yy)$; or $v_p(t_yy) = v_p(t_zz)\le v_p(t_xx)$. If $v_p(t_xx) = v_p(t_yy)$, then $d + v_p(x) = v_p(y)$, hence, $\chi_1(x)\neq \chi_1(y)$, which contradicts $\chi(x) = \chi(y)$. If $v_p(t_xx) = v_p(t_zz)$, then $d + v_p(x) = v_p(z)$, hence, $\chi_1(x)\neq \chi_1(z)$, which contradicts $\chi(x) = \chi(z)$. So, assume that $v_p(t_yy) = v_p(t_zz)\le v_p(t_xx)$. Recalling our coefficients, we obtain $v_p(y) = v_p(z) \le d + v_p(x)$. By (the second part of) Lemma \ref{v_p}, we also have $v_p(2y-z) = d + v_p(x)$. Let $e$ denote the common value of $v_p(y)$ and $v_p(z)$. Let $y=y'p^{e}$ and $z = z'p^{e}$. Since $\chi_2(y) = \chi_2(z)$, then $\chi_2'(y'\mbox{ mod }p) = \chi_2'(z'\mbox{ mod }p)$, hence, $2y'-z' \not\equiv 0\pmod{p}$. However, this implies $v_p(2y-z) = e$, so $v_p(y) = v_p(z) = e = d + v_p(x)$. It follows from here that $\chi_1(x)$ is different from $\chi_1(y)$ and $\chi_1(z)$, which contradicts $\chi(x) = \chi(y) = \chi(z)$. Since $v_p(0) = +\infty$ and there are no $x$, $y$, $z$, all of the same color and $v_p(t_xx+t_yy+t_zz) > \mbox{max}\{v_p(t_xx), v_p(t_yy), v_p(t_zz)\}$, then, in particular, there are no monochromatic solutions to $t_xx+t_yy+t_zz = 0$ (i.e. $(b-2a)x+2y-z=0$) in $\chi$. Case B is essentially equivalent to Lemma 6 (with $s=1$) in \cite{FoKl}. Notice that one can define $\chi_2$ to be a 2-coloring in the proof above, as long as the order of $2 \mbox{ mod }p$ is even. \noindent{{\bf Case C.}} $t_x\in \{-2, -1, 1, 2\}$ Case $t_x = -1$ is taken care of in \cite{LaRo}, as mentioned before, while cases $t_x = 1$ and $t_x = -2$ correspond to Cases 1 and 2, respectively. The only remaining case is $t_x = 2$.\footnote{The equation is not regular in this case, however this possibility is not covered by Cases A and B of the improved upper bound analysis.} In this case, we have $y=ax+d$ and $z=(2a+2)x+2d$. Therefore, $2y 2$. %They guess that $\mbox{dor}(a,b)=2$ for $(a,b) \not =(1,1)$ and $b %\not =2a$, although they have scant evidence. Theorem \ref{thm} %gives support in that direction. After submission, we learned that Frantzikinakis, Landman, and Robertson \cite{FrLaRo} independently showed that $\mbox{dor}(a,b)$ is finite unless $(a,b) = (1,1)$. \begin{thebibliography}{} \footnotesize \bibitem{BeLi} V. Bergelson and A. Leibman, \newblock Polynomial extensions of van der Waerden's and Szemer\'edi's theorems, \newblock {\em J. Amer. Math. Soc.} {\bf 9} (1996) 725--753. \bibitem{BrGrLa} T. C. Brown, R. L. Graham, and B. M. Landman, \newblock On the set of common differences in van der Waerden's theorem on arithmetic progressions, \newblock {\em Canad. Math. Bull.} {\bf 42} (1999), 25--36. \bibitem{BrLaMi} T. C. Brown, B. M. Landman, and M. Mishna, \newblock Monochromatic homothetic copies of $\{1, 1 + s, 1 + s + t\}$, \newblock {\em Canadian Math. Bull.} {\bf 40} (1997), 149--157. \bibitem{FoKl} J. Fox and D. Kleitman, \newblock On Rado's Boundedness Conjecture, \newblock {\em Journal of Combinatorial Theory, Series A}, accepted. \bibitem{FrLaRo} N. Frantzikinakis, B. Landman, A. Robertson, \newblock On the degree of regularity of generalized van der Waerden triples, \newblock {\em Advances in Applied Math.}, accepted. \bibitem{Fu} H. Furstenberg, \newblock {\em Recurrences in Ergodic Theory and Combinatorial Number Theory}. Princeton University Press, Princeton, 1981. \newblock \bibitem{Go} T. Gowers, \newblock A new proof of Szemer\'edi's theorem, \newblock {\em Geometric and Functional Analysis}, {\bf 11} (2001) 465--588. \bibitem{GrRoSp} R. L. Graham, B. L. Rothschild, and J. Spencer, \newblock {\em Ramsey Theory}. John Wiley \& Sons Inc., New York, 1990. \newblock \bibitem{HiLeSt} N. Hindman, I. Leader, and D. Strauss, \newblock Open problems in partition regularity, \newblock {\em Combinatorics, Probability, and Computing}, {\bf 12} (2003) 571--583. \bibitem{LaRo} B. M. Landman and A. Robertson, \newblock On generalized van der Waerden triples, \newblock {\it Discrete Mathematics} {\bf 256} (2002) 279--290. \bibitem{LaRo1} B. M. Landman and A. Robertson, \newblock {\em Ramsey theory on the integers.} \newblock Student Mathematical Library, 24. American Mathematical Society, Providence, RI, 2004. (Research Problem 5.4, p. 159.) \bibitem{Ra} R. Rado, \newblock Studien zur Kombinatorik, \newblock {\it Math. Zeit.} {\bf 36} (1933) 242--280. \bibitem{Sc} I. Schur, \newblock Uber die Kongruenze $x^m +y^m \equiv z^m$ (mod $p$), \newblock {\em Jber. Deutsch. Math.-Verein.} {\bf 25} (1916), 114--117. %\bibitem{Sh} %S. Shelah, %\newblock Primitive recursive bounds for van der Waerden numbers, %\newblock {\em J. Amer. Math. Soc.} {\bf 1} (1988), 683--697. \bibitem{Sz} E. Szemer\'edi, \newblock On sets of integers containing no $k$ elements in arithmetic progression, \newblock {\em Acta Arith.} {\bf 27} (1975), 199--245. \bibitem{Wa} B. L. van der Waerden, \newblock Beweis einer Baudetschen Vermutung, \newblock {\em Nieuw Arch. Wisk.} {\bf 15} (1927), 212--216. % \bibitem[Names(Year)]{label} or \bibitem[Names(Year)Long names]{label}. % (\harvarditem{Name}{Year}{label} is also supported.) % Text of bibliographic item \end{thebibliography} \end{document}