%%%% THIS FILE IS AUTOMATICALLY GENERATED %%%% DO NOT EDIT THIS FILE DIRECTLY, %%%% ONLY EDIT THE SOURCE, tom-6/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 \newcounter{c1} \newcounter{c2} \newcounter{c3} \newcounter{c4} \newtheorem{thrm}[c1]{Theorem} \newtheorem{corl}[c2]{Corollary} \newtheorem{lmma}[c3]{Lemma} \newtheorem{defn}[c4]{Definition} \title{A coloring of the non-negative integers, with applications} \author{Tom C. Brown ~\\~\\ \small Department of Mathematics\\ \small ¶¡ÏãÔ°AV\\ \small Burnaby, BC\\ \small Canada V5A 1S6\\ \small \texttt{tbrown@sfu.ca} } \maketitle \begin{center}{\small {\bf Citation data:} T.C. {Brown}, \emph{A partition of the non-negative integers, with applications}, INTEGERS - Elect. J. Combin. Number Theory \textbf{5} (2005), no. 2, A2, (Proceedings of the Integers Conference 2003 in Honor of Tom Brown's Birthday).}\bigskip\end{center} \begin{abstract}We describe a particular partition of the non-negative integers which consists of infinitely many translates of an infinite set. This partition is used to show that a certain van der Waerden-like theorem has no simple canonical version. The partition is also used to give a lower bound for one of the classical van der Waerden functions, namely $w(3;m)$, the smallest positive integer such that every $m$-coloring of $[1, w(3;m)]$ produces a monochromatic 3-term arithmetic progression. Several open questions are mentioned. \end{abstract} \section*{Introduction} Let $S$ denote the set of all distinct sums of odd powers of 2, including 0 as the empty sum. Then every non-negative integer can be written uniquely in the form $s + t$, where $s\in S$ and $t\in T$, and define $f(n) = s$. In other words, if $n = \sum_{i\text{ odd}}2^i + \sum_{i\text{ even}}2^i$, then $f(n) = \sum_{i\text{ odd}}2^i$. For this coloring $f$, the set of colors is $S$, and for each $s\in S$, $f$ is constant on the ``color class'' $s + T$. \section*{A van der Waerden-like theorem, and its canonical version} We need the following definition. \begin{defn} If $A = \{ a_1 < a_2 < \cdots < a_n\} \subset \omega = \{0,1,2,\ldots\}$, $n \geq 2$, the \emph{gap size} of $A$ is $\gs(A) = \max\{a_{j+1} - a_j : 1\leq j \leq n - 1\}$. If $|A| = 1$, $\gs(A) = 1$.\end{defn} \begin{thrm} If $\omega$ is finitely colored, there exist a fixed $d\geq 1$ ($d$ depends only on the coloring) and arbitrarily large (finite) monochromatic sets $A$ with $\gs(A) = d$.\label{vanhal}\end{thrm} This fact first appeared in \cite{brown1968}. A proof can be found in \cite{landman+robertson2004}. Various applications appear in \cite{brown1971-1,deluca+varricchio1998,lallement1979,straubing1982}. Theorem \ref{vanhal} is somewhat similar in form to van der Waerden's theorem on arithmetic progressions \cite{vanderwaerden1927}. (Van der Waerden's theorem says that for every $k$, every finite coloring of the positive integers produces a monochromatic $k$-term arithmetic progression.) However, Theorem \ref{vanhal} differs in a number of ways: Van der Waerden's theorem does not imply Theorem~\ref{vanhal}, since the $d$ in the conclusion of Theorem~\ref{vanhal} is independent of the size of the monochromatic sets $A$. Beck \cite{beck1980} showed the existence of a 2-coloring of $\omega$ such that if $A$ is any monochromatic arithmetic progression with common difference $d$, then $|A| < 2\log d$. Hence the presence of large monochromatic arithmetic progressions, which is guaranteed by van der Waerden's theorem, is not enough to imply Theorem \ref{vanhal}. Somewhat earlier, Justin \cite{justin1971} found an explicit coloring such that if $A$ is any monochromatic arithmetic progression with common difference $d$, then $|A| < h(d)$; in his example, the coloring is explicit but the function $h(d)$ is not. Theorem \ref{vanhal} (which has a simple proof) does not imply van der Waerden's theorem in a simple way. (In Chapter 14 of \cite{hindman+strauss1998}, Hindman and Strauss give a proof that Fact 1 does in fact imply van der Waerden's theorem -- and at this point in their book, the proof \emph{does} seem simple -- however, a fair amount of machinery has been developed by this point.) Theorem \ref{vanhal} does not have a density version corresponding to Szemer\'edi's theorem \cite{szemeredi1975}. That is, there exists a set $X\subset\omega$ with positive upper density for which there do \emph{not} exist a fixed $d \geq 1$ and arbitrarily large sets $A = \{ a_1 < a_2 < \cdots < a_n \} \subset X$ with $\gs(A) = d$. For an example of such a set $X$, see \cite{bergelson+hindman+mccutcheon1998}. Finally, no ``canonical version'' of this result is known. The Erd\H{o}s-Graham canonical version of van der Waerden's theorem (\cite{erdos+graham1980}) states that if $g: \omega\to\omega$ is an arbitrary coloring of $\omega$ (using finitely many or infinitely many colors) then there exist arbitrarily large arithmetic progressions $A$ such that either $g$ is constant on $A$, i.e. $|g(A)| = 1$, or $g$ is one-to-one on $A$, i.e. $|g(A)| = |A|$. We show that there is no such canonical version of Theorem \ref{vanhal}. This is Corollary \ref{cologne} below. A very brief sketch of an outline of a proof of the following result has appeared in \cite{brown2003}. It seems worthwhile to fill in some of the missing details. \begin{thrm} For every $A\subset\omega$ (with $f$ as described in the introduction), \[ \frac14\sqrt{|A|/\gs(A)} < |f(A)| < 4\sqrt{|A|\gs(A)} \] \label{tewinkel}\end{thrm} \begin{corl} For the coloring $f$ above, there do not exist a fixed $d$ and arbitrarily large sets $A$ with $\gs(A) = d$ on which $f$ is either constant or 1-1.\label{cologne}\end{corl} \begin{proof}[Proof of Corollary \ref{cologne}] If $16\gs(A) \leq |A|$, then by Theorem \ref{tewinkel}, $1 < |f(A)| < |A|$.\end{proof} To prove Theorem \ref{tewinkel}, we need the following definition. \begin{defn} For $k\geq 0$, an \emph{aligned block} of size $4^k$ is a set of $4^k$ consecutive non-negative integers whose smallest element is $m4^k$, for some $m\geq 0$.\end{defn} \begin{proof}[Proof of Theorem \ref{tewinkel}] Note that the first aligned block of size $4^k$, namely $[0, 4^k-1] = [0, 2^{2k} - 1]$, is in 1-1 correspondence with the set of all binary sequences of length $2k$. From this we see (by the definition of $f$) that for $n\in[0,2^{2k}-1]$, there are $2^k$ possible values of $f(n)$, and each value occurs exactly $2^k$ times. It is easy to see (using the definition of $f$) that the same is true for any aligned block $[m4^k, m4^k + 4^k - 1]$. We express this more simply by saying that \emph{``each aligned block of size $4^k$ has $2^k$ colors, each appearing exactly $2^k$ times.''} Now we can establish the upper bound in Theorem \ref{tewinkel}. Let $A = \{ a_0 < a_1 < a_2 < \cdots < a_n \} \subset \omega$. Then $a_n \leq a_0 + n\gs(A) = a_0 + (|A| - 1)\gs(A)$, or \[ a_n - a_0 < |A|\gs(A). \] Choose $s$ minimal so that $A$ is contained in the union of two adjacent aligned blocks of size $4^s$. (Two blocks are necessary in case $A$ contains both $m4^s - 1$ and $m4^s$ for some $m$.) Then \[ 4^{s-1} < a_n - a_0. \] Since each aligned block of size $4^s$ has $2^s$ colors, \[ |f(A)| \leq 2\cdot2^s. \] Putting these three inequalities together gives \[ |f(A)| < 4\sqrt{|A|\gs(A)}. \] Next, we establish the lower bound for $|f(A)|$, which requires a bit more care. We will use the following Lemma. \begin{lmma} For each $k \geq 0$, an two aligned blocks of size $4^k$ (consecutive or not) are either colored identically, or have no color in common.\label{wuttke}\end{lmma} \begin{proof}[Proof of Lemma \ref{wuttke}] Consider the aligned blocks $[p4^k, p4^k + 4^k - 1]$ and $[q4^k, q4^k + 4^k - 1]$. By the definition of $f$ (and since $4^k$ is an even power of 2), $f(p4^k) = f(p)4^k$, so that $f(p4^k) = f(q4^k)$ if and only if $f(p) = f(q)$. Also, for $0\leq j\leq4^k - 1$, $f(p4^k + j) = f(p4^k) + f(j)$. This last equality obviously holds if $p = 0$, and for $p > 0$ it holds since then each power of 2 which occurs in $j$ is less than each power of 2 which occurs in $p4^k$. Thus the blocks $[p4^k, p4^k + 4^k - 1]$ and $[q4^k, q4^k + 4^k - 1]$ are colored identically if $f(p) = f(q)$, and have no color in common if $f(p) \neq f(q)$. Proceeding with the lower bound in Theorem \ref{tewinkel}, we note that for $k \geq 1$, the colors of any aligned block of size $4^k$ have the form $UUVV$, where $U$ and $V$ are blocks of size $4^{k-1}$. Next, we note that any block of size $4^k$, aligned or not, contains \emph{at least} $2^k$ colors. for let $A$ be any block of size $4^k$. Let the first element of $A$ lie in the aligned block $S$ of size $4^k$, and let $T$ be the aligned block of size $4^k$ which immediately succeeds $S$. If $S$ and $T$ are colored identically, then the elements of $f(A)$ are just a cyclic permutation of the elements of $f(S)$, and hence the block $A$ contains exactly $2^k$ colors. By Lemma \ref{wuttke}, the remaining case is when $S$,$T$ have no color in common. In this case, by the preceding paragraph, $f(S)f(T) = UUVVXXYY$, where no two of $U,V,X,Y$ have a color in common, and so $U,V,X,Y$ are of size $4^{k-1}$. Then $f(A)$, which has size $4^k$, contains either $UV$ or $VX$ or $XY$, and so has at least $2^{k-1} + 2^{k-1} = 2^k$ colors. Finally, we note that for $s \geq 1$, $k\geq 1$, every set of $4^s$ consecutive aligned blocks of size $4^k$ contains at least $2^s$ blocks of size $4^k$, no two of which have a common color. This follows from the fact that these $p^s$ blocks have the form $[p4^k, p4^k + 4^k - 1]$, $t \leq p \leq t + 4^s - 1$, for some $t$. The block $f$ $([t,t + 4^s - 1])$ has at least $2^s$ colors, by the preceding paragraph. If $f(p)\neq f(q)$, where $t\leq p < q\leq t + 4^s - 1$, then $f(p4^k)\neq f(q4^k)$, so by Lemma \ref{wuttke} the two blocks $[p4^k, p4^k + 4^k - 1]$ and $[q4^k, q4^k + 4^k - 1]$ have no color in common. Now let $A\subset\omega$ be given. Choose $k$ so that $4^{k-1}\leq \gs(A)<4^k$. Choose $t$ minimal so that $A$ is contained in the union of $t$ consecutive aligned blocks of size $4^k$. Then $A$ meets each of these blocks (by the choice of $k$), and \[ |A| \leq t4^k. \] Choose $s$ so that $4^s\leq t < 4^{s+1}$. Then among the $t$ consecutive aligned blocks of size $4^k$ are at least $2^s$ blocks of size $4^k$, no two of which have a color in common. Since each of the $t$ blocks meets $A$, we have \[ 2^s \leq |f(A)|. \] Thus $|A|\leq t4^k < 4\cdot4^s\cdot4\cdot4^{k-1}\leq 4|f(A)|^2\cdot4\cdot\gs(A)$, so $\frac14\sqrt{|A|/\gs{A}} < |f(A)|$.\end{proof}\qedhere \end{proof} \section*{A bound for a van der Waerden function} \begin{defn}For $m\geq 1$, let $w(3;m)$ denote the smallest positive integer such that every $m$-coloring of $[1,w(3;m)]$ produces a monochromatic 3-term arithmetic progression.\end{defn} \begin{thrm} For all $m\geq1$, $w(3;m) > \frac12m^2$.\end{thrm} \begin{proof} For $k\geq1$, the coloring $f$ described in the introduction colors the interval $[0,2^{2k+1} - 1]$ with $2^k$ colors. The colors are the sums (including 0 as the empty sum) of distinct elements of the set $\{2^1, 2^3,2^5,\ldots,2^{2k-1}\}$. The color classes are subsets of the translates (by the $2^k$ colors) of the set $S_k$ of sums (including 0 as the empty sum) of distinct elements of the set $\{2^0,2^2,2^4,\ldots,2^{2k}\} = \{4^0,4^1, 4^2,\ldots,4^k\}$. It is easy to see that $S_k$ contains no 3-term arithmetic progression. Hence, with respect to the coloring $f$, there is no monochromatic 3-term arithmetic progression in $[0,2^{2k+1}-1]$. The coloring $f$ shows that for $k\geq1$, $w(3;2^k) > 2^{2k+1}$. For a general $m$, choose $k$ so that $2^k\leq m< 2^{k+1}$. Then $w(3;m)\geq w(3;2^k) > 2^{2k+1} = \frac122^{2k+2} < \frac12m^2$. \end{proof} \section*{Remarks} \begin{enumerate} \item The lower bound in Theorem 3 is not the best possible. Indeed, in the standard reference Ramsey Theory (by R. L. Graham, B. L. Rothschild, and J. H. Spencer, 2nd edition, 1990, John Wiley \& Sons, New York), the authors show that for some positive constant $c$, $w(3;m) > m^{(c\log m)}$. \item Of course, one would like to have an upper bound for the function $w(3;m)$. The only bound known to me is $w(3;m) < \left(\frac{m}4\right)^{3^m}$ for $m>4$. This bound comes from \cite{huang+yang2000}, and is mentioned in \cite{landman+robertson2004}. The coloring $f$ on $[0,2^{2k+1}-1]$, with $2^k$ colors, is perhaps ``efficient'' in stopping all monochromatic 3-term arithmetic progressions. Cutting the number of colors in half would seem to leave too few colors. If this were in fact true, then $w(3;2^{k-1}) \leq2^{2k+1}$ would follow, and for general $m$ one would then have $\frac12m^2 < w(3;m) < 8m^2$. \item Corollary \ref{cologne} shows that a constant/1-1 canonical version of Theorem \ref{vanhal} is not true. We also know by the Bergelson/Hindman/McCutcheon example that a density version of Theorem \ref{vanhal} is not true. The following three simple examples, involving only 3-element sets, illustrate various combinations of the truth or falsity of the ``constant/1-1 versions'' and the ``density versions.'' \begin{enumerate} \item The simplest non-trivial case of van der Waerden's theorem says that every finite coloring of the positive integers produces a monochromatic 3-term arithmetic progression. The constant/1-1 version of this reselt holds by the Erd\H{o}s-Graham theorem, and the density version holds by Szemer\'edi's theorem. \item Schur's theorem says that if the positive integers are finitely colored, then there is a monochromatic solution of $x + y = z$. The density version does not hold by taking all the odd integers. The constant/1-1 version does not hold by coloring each $x$ with the highest power of 2 dividing $x$. \item At the meeting, Kevin O'Bryant showed me this example: if the positive integers are finitely colored, then there is a monochromatic 3-term geometric progression (a set of the form $\{a, ad, ad^2\}$). To get the constant/1-1 version, let a coloring $g$ of the positive integers be given. define a new coloring $h$ by setting $h(x) = g(2^x)$. Then, by the Erd\H{o}s-Graham theorem, there is a set $\{a, a+d, a+2d\}$ on which the coloring $h$ is either constant or 1-1. The density version does not hold, since the set of square-free numbers has positive density. \item It seems natural to ask for a collection $P$ of 3-element sets (if such a collection exists!) for which: (i) Every set of positive integers with positive upper density contains an element of $P$; (ii) It's not the case that for every coloring of the positive integers, there is an element of $P$ on which the coloring is either constant or 1-1. \end{enumerate} \item It would be nice to be able to say \emph{something} about general colorings along the lines of Theorem \ref{vanhal}. Perhaps the following is true: if $\omega\to \omega$ is an arbitrary coloring of $\omega$, then there exist a fixed $d\geq 1$ and arbitrarily large (finite) sets $A$ with $\gs(A) = d$ such that either \begin{enumerate} \item at most $\sqrt{|A|}$ distinct colors appear in $g|_A$; or \item each color appears in $g|_A$ at most $\sqrt{|A|}$ times. \end{enumerate} Note that for the particular coloring $f$, if we take $d = 1$, and let $A = [0,4^k-1]$, then exactly $\sqrt{|A|}$ distinct colors appear in $f|_A$, and each color appears in $f|_A$ exactly $\sqrt{|A|}$ times. \item We have used a particular partition of $\omega$. We would get another partition of $\omega$ (into infinitely many translates of an infinite set) by replacing the odd powers of 2 and the even powers of 2 by arbitrary $A$ and $B$, where $\{A,B\}$ is any partition of $\{1,2,3,\ldots\}$ into two infinite sets. Perhaps it's possible to describe \emph{all} of the partitions of $\omega$ into infinitely many translates of an infinite set. \end{enumerate} \bibliographystyle{amsplain} \bibliography{tom-all} \end{document}