\documentclass[12pt]{article} \usepackage{e-jc} \usepackage{amssymb,amsmath,amstext,amsthm,amsfonts} \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} \vfuzz2pt \usepackage{pstricks,pstricks-add,pst-math,pst-xkey} \usepackage{graphics} \usepackage{epsfig} \newcommand{\C}{\mathbb{C}} \newcommand{\R}{\mathbb{R}} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{fact}[theorem]{Fact} \newtheorem{observation}[theorem]{Observation} \newtheorem{claim}[theorem]{Claim} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{open}[theorem]{Open Problem} \newtheorem{problem}[theorem]{Problem} \newtheorem{question}[theorem]{Question} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{note}[theorem]{Note} \title{\bf The gap structure of a family of integer subsets} \author{Andr\'{e} Bernardino.\\ \small Departamento de Matem\'{a}tica\\[-0.8ex] \small Universidade da Beira Interior\\[-0.8ex] \small Covilh\~{a}, Portugal.\\ \small\tt and\_bernardino@hotmail.com\\ Rui Pacheco.\\ \small Departamento de Matem\'{a}tica\\[-0.8ex] \small Universidade da Beira Interior\\[-0.8ex] \small Covilh\~{a}, Portugal.\\ \small\tt rpacheco@ubi.pt\\ Manuel Silva\\ \small Departamento de Matem\'{a}tica\\[-0.8ex] \small Universidade Nova de Lisboa\\[-0.8ex] \small Caparica, Portugal.\\ \small\tt mnas@fct.unl.pt} \date{\dateline{Jan 1, 2012}{Jan 2, 2012}\\ \small Mathematics Subject Classifications: 11B25, 05D10} \begin{document} \maketitle \begin{abstract} In this paper we investigate the gap structure of a certain family of subsets of $\mathbb{N}$ which produces counterexamples both to the ``density version" and the ``canonical version" of Brown's lemma. This family includes the members of all complementing pairs of $\mathbb{N}$. We will also relate the asymptotical gap structure of subsets of $\mathbb{N}$ with their density and investigate the asymptotical gap structure of monochromatic and rainbow sets with respect to arbitrary infinite colorings of $\mathbb{N}$. \bigskip\noindent \textbf{Keywords:} piecewise syndetic, complementing pairs, Brown's lemma, Ramsey theory. \end{abstract} \section{Introduction}\label{intro} Let $\mathbb{N}$ be the set of all nonnegative integers. The \emph{gap} of a finite subset $A=\{a_1,\ldots,a_k\}$ of $\mathbb{N}$ is the number $\mathrm{gap}(A):=\max \{a_{i+1}-a_i:\,1\leq i\leq k-1\}.$ An infinite subset $X$ of $\mathbb{N}$ is \emph{piecewise syndetic} if it contains arbitrarily large subsets with uniformly bounded gaps. This means that the sequence in $k\in \mathbb{N}$ defined by \begin{equation}\label{asgap} d_k(X):=\min\{\mathrm{gap}(A):\, A\subset X\,\,\mathrm{and}\,\,|A|=k+1 \}, \end{equation} is bounded. An induction argument in the number of colors shows \cite{Br1,Br2} that any finite coloring of $\mathbb{N}$ admits a monochromatic piecewise syndetic set. This result is known as \emph{Brown's lemma}. Brown's lemma does not admit a density version analogous to Szemer\'{e}di's theorem \cite{S}, that is, there are subsets $X$ of $\mathbb{N}$ with positive density which are not piecewise syndetic. An example of such a subset is given in \cite{BHM}, Theorem 2.8. Brown's lemma also does not admit a canonical version analogous to the Erd\H{o}s-Graham canonical version of van der Waerden's theorem \cite{EG}. In fact, T. Brown \cite{Br4,Br3} showed that there is an infinite coloring $\tau:\mathbb{N}\to \mathbb{N}$ for which the sequence in $k\in\mathbb{N}$ defined by \begin{equation}\label{asgap1} d_k(\tau):=\min\{\mathrm{gap}(A):\,|A|=k+1 \,\,\mbox{and either $|\tau(A)|=1$ or $|\tau(A)|=k+1$}\} \end{equation} is not bounded. The infinite coloring used by T. Brown consists of infinitely many translates of an infinite set, that is, it is a coloring associated to a certain \emph{complementing pair} of $\mathbb{N}$. Two infinite subsets $X_1$ and $X_2$ of $\mathbb{N}$ are a complementing pair of $\mathbb{N}$, and we write $\mathbb{N}=X_1\oplus X_2$, if for each $n\in \mathbb{N}$ there exist unique $n_1\in X_1$ and $n_2\in X_2$ such that $n=n_1+n_2$. In this case we can define an infinite coloring $\tau:\mathbb{N}\to\mathbb{N}$ by $\tau(n)=n_2$. In this paper we will investigate the gap structure of a certain family of subsets of $\mathbb{N}$ which produces counterexamples both to the ``density version" and the ``canonical version" of Brown's lemma. This family includes the members of all complementing pairs of $\mathbb{N}$. We will also investigate the asymptotical upper bounds of $d_k(X)$ and $d_k(\tau)$ when $X$ is a subset of $\mathbb{N}$ with positive upper density and $\tau$ is an infinite coloring of $\mathbb{N}$. \section{A familiy of non-piecewise syndetic sets with positive density} We will denote by $\overline{\sigma}(X)$ and $\underline{\sigma}(X)$, respectively, the \emph{upper density} and the \emph{lower density} of $X$: \begin{equation*} \overline{\sigma}(X):=\limsup_n\frac{|X\cap [0,n]|}{n},\,\, \mbox{and}\,\,\,\, \underline{\sigma}(X):=\liminf_n\frac{|X\cap [0,n]|}{n}. \end{equation*} If $\overline{\sigma}(X)=\underline{\sigma}(X)$, the \emph{density} of $X$ is equal to this common value and is denoted by $\sigma(X)$. Consider two infinite sequences $a_n$ and $d_n$ of positive integers, with $a_0=1$. Assume that $a_n$ is strictly increasing, $d_n$ is nondecreasing and $\frac{a_{n+1}}{a_n}$ is an integer for each $n\in\mathbb{N}$. Fix an integer $K>0$. We define recursively an increasing sequence of finite subsets $I_n:=I_n(a_n,d_n,K)$ of $\mathbb{N}$, with $\beta_n:=\max \,I_n$, as follows: $I_0=[0,K]$ and \begin{equation}\label{in} I_n=I_{n-1}\cup \{\beta_{n-1}+d_n+I_{n-1}\}\cup\ldots\cup \Big\{\big(\frac{a_n}{a_{n-1}}-1\big)\beta_{n-1}+\big(\frac{a_n}{a_{n-1}}-1\big)d_n+I_{n-1}\Big\}. \end{equation} Set $\mathcal{I}=\bigcup_{n\in\mathbb{N}}I_n$. Observe that $|I_n|=\frac{a_n}{a_{n-1}}|I_{n-1}|$ and $$\beta_n=\frac{a_n}{a_{n-1}}\beta_{n-1}+\big(\frac{a_n}{a_{n-1}}-1\big)d_n.$$ Hence \begin{equation}\label{rec} |I_n|=a_n (K+1)\quad\quad\mathrm{and}\quad\quad \beta_n=a_nK+a_n\sum_{i=1}^n{\big(\frac{1}{a_{i-1}}-\frac{1}{a_i}\big)}d_i. \end{equation} \begin{example}\label{exa} If $a_n=2^n$, then $I_0=[0,K]$, $I_1=I_0\cup \{d_1+K+I_0\}$, $I_2=I_1\cup\{d_2+d_1+2K+I_1\}$, and the structure of $I_3$ is illustrated by the following figure. \begin{figure}[h!] \begin{center} \psset{xunit=0.7cm,yunit=0.7cm,algebraic=true,dotstyle=o,dotsize=3pt 0,linewidth=0.5pt,arrowsize=3pt 2,arrowinset=0.25} \begin{pspicture*}(-0.24,-0.3)(19.7,3) \psline[linewidth=4pt](0,0)(1,0) \psline[linewidth=4pt](2,0)(3,0) \psline[linewidth=4pt](5,0)(6,0) \psline[linewidth=4pt](7,0)(8,0) \psline[linewidth=4pt](11,0)(12,0) \psline[linewidth=4pt](13,0)(14,0) \psline[linewidth=4pt](16,0)(17,0) \psline[linewidth=4pt](18,0)(19,0) \rput[tl](0.42,0.8){$I_0$} \parametricplot{0.0}{3.141592653589793}{1*0.5*cos(t)+0*0.5*sin(t)+1.5|0*0.5*cos(t)+1*0.5*sin(t)+0} \psline(2,0)(1.98,0.32) \psline(2,0)(1.98,0.32) \psline(2,0)(1.83,0.23) \parametricplot{0.0}{3.141592653589793}{1*1*cos(t)+0*1*sin(t)+4|0*1*cos(t)+1*1*sin(t)+0} \parametricplot{0.0}{3.141592653589793}{1*0.5*cos(t)+0*0.5*sin(t)+6.5|0*0.5*cos(t)+1*0.5*sin(t)+0} \parametricplot{0.0}{3.141592653589793}{1*1.5*cos(t)+0*1.5*sin(t)+9.5|0*1.5*cos(t)+1*1.5*sin(t)+0} \parametricplot{0.0}{3.141592653589793}{1*0.5*cos(t)+0*0.5*sin(t)+12.5|0*0.5*cos(t)+1*0.5*sin(t)+0} \parametricplot{0.0}{3.141592653589793}{1*1*cos(t)+0*1*sin(t)+15|0*1*cos(t)+1*1*sin(t)+0} \parametricplot{0.0}{3.141592653589793}{1*0.5*cos(t)+0*0.5*sin(t)+17.5|0*0.5*cos(t)+1*0.5*sin(t)+0} \psline(5,0)(4.85,0.26) \psline(5,0)(5.02,0.3) \psline(7,0)(7.02,0.24) \psline(7,0)(7.02,0.24) \psline(7,0)(6.88,0.2) \psline(11,0)(11.06,0.24) \psline(11,0)(10.92,0.22) \psline(13,0)(13.03,0.23) \psline(13,0)(12.88,0.18) \psline(16,0)(16.04,0.23) \psline(16,0)(15.89,0.2) \psline(18,0)(18.04,0.2) \psline(18,0)(17.89,0.15) \rput[tl](3.95,1.71){$d_2$} \rput[tl](6.36,1.25){$d_1$} \rput[tl](1.45,1.21){$d_1$} \rput[tl](9.35,2.33){$d_3$} \rput[tl](12.35,1.25){$d_1$} \rput[tl](14.85,1.75){$d_2$} \rput[tl](17.39,1.2){$d_1$} \end{pspicture*} \end{center} \end{figure} \end{example} \begin{lemma}\label{convdiv} The subset $\mathcal{I}(a_n,d_n,K):=\mathcal{I}=\bigcup_{n\in\mathbb N}I_n$ of $\mathbb{N}$ has positive upper density if and only if the positive series \begin{equation}\label{series} \sum_{i=1}^\infty{\big(\frac{1}{a_{i-1}}-\frac{1}{a_i}\big)}d_i \end{equation} converges. Moreover, $\overline{\sigma}(\mathcal{I})=\underline{\sigma}(\mathcal{I})$. \end{lemma} \begin{proof}Taking into account \eqref{rec} we have \begin{align*} x_n:=\frac{\left|I_n\right|}{\beta_n}= \frac{K+1}{K+\sum_{i=1}^n{\big(\frac{1}{a_{i-1}}-\frac{1}{a_i}\big)}d_i}. \end{align*} This sequence is always convergent and $$x_n= \sup \Big\{\frac{\left|\mathcal{I}\cap[0,N]\right|}{N}:\, N\geq \beta_n\Big\}.$$ This means that the largest limit of subsequences of $\frac{\left|\mathcal{I}\cap[0,n]\right|}{n}$ is attained by $x_n$. Hence \begin{equation*} \overline{\sigma}(\mathcal{I})=\lim_n \frac{K+1}{K+\sum_{i=1}^n{\big(\frac{1}{a_{i-1}}-\frac{1}{a_i}\big)}d_i}, \end{equation*} which means that $\overline{\sigma}(\mathcal{I})>0$ if and only if the series \eqref{series} converges. If the series \eqref{series} diverges, then it is clear that $\overline{\sigma}(\mathcal{I})=\underline{\sigma}(\mathcal{I})=0$. Assume now that the series \eqref{series} converges. In this case $$0=\lim_n(\frac{1}{a_{n-1}}-\frac{1}{a_n})d_n=\lim_n \frac{1}{a_{n}}\big(\frac{a_n}{a_{n-1}}-1\big)d_n\geq \lim_n \frac{d_n}{a_n},$$ that is $\lim_n \frac{d_n}{a_n}=0$. On the other hand, $$y_n:=\frac{\left|I_n\right|}{\beta_n+d_n-1}= \min \Big\{\frac{\left|\mathcal{I}\cap[0,N]\right|}{N}:\, N\leq \beta_n+d_n-1\Big\}.$$ Since $\lim_n \frac{d_n}{a_n}=0$, we have $\lim x_n=\lim y_n$, that is the smallest limit of subsequences of $\frac{\left|\mathcal{I}\cap[0,n]\right|}{n}$ is attained by $y_n$ and it is equal to $\overline{\sigma}(\mathcal{I})$. \end{proof} \begin{remark} Given sequences $a_n$ and $d_n$ for which \eqref{series} converges, we can make $\overline{\sigma}(\mathcal{I})$ arbitrarily close to $1$ by taking $K\to \infty$. \end{remark} \begin{remark} Taking into account its construction, if $\lim d_n=\infty$ the subset $\mathcal{I}$ is not piecewise syndetic. For example, if $a_n=2^n$ and $d_n=n$, $\mathcal{I}$ is not piecewise syndetic but it has positive density $\frac{K+1}{K+2}$. \end{remark} This family of subsets is optimal in the following sense. \begin{lemma}\label{iopt} For each $n\in \mathbb{N}$, we have $d_{a_n(K+1)}(\mathcal{I})=d_{n+1}$. Moreover, given $X\subset \mathbb{N}$, then $\overline{\sigma}{(X)}\leq {\sigma}{(\mathcal{I})}$ if $d_{a_n(K+1)}(X)\geq d_{n+1}$ for each $n\in\mathbb{N}$. \end{lemma} \begin{proof} The first assertion follows directly from the definitions of $\mathcal{I}$ and $d_{k}(\mathcal{I})$. With the respect to the second assertion, observe that, for each $k\in \mathbb{N}$, we have $d_k(\mathcal{I})=d_{a_{n_k}(K+1)}(\mathcal{I})$, where $$n_k=\max\{n:\,a_n(K+1)\leq k\}.$$ This means that, if $d_{a_n(K+1)}(X)\geq d_{n+1}$, then $d_k(X)\geq d_k(\mathcal{I})$ for all $k$, and consequently $\overline{\sigma}{(X)}\leq \overline{\sigma}{(\mathcal{I})} ={\sigma}{(\mathcal{I})}$. \end{proof} \section{Complementing pairs of $\mathbb{N}$.} Complementing pairs of $\mathbb{N}$ admit the following characterization (see \cite{Ti} and the references therein). Given two infinite subsets $X_1$ and $X_2$ of $\mathbb{N}$, we have $\mathbb{N}=X_1\oplus X_2$ if and only if there exists a sequence $m_i$, with $m_i\geq 2$ for all $i\in \mathbb{N}$, such that $X_1$ is the set of all finite sums $\sum_{i\geq 0} x_{2i} M_{2i}$ and $X_2$ is the set of all finite sums $\sum_{i\geq 0} x_{2i+1} M_{2i+1}$, where $M_0=1$, $M_i=\prod_{j=1}^im_j$ and $0\leq x_i< m_{i+1}$. Let $$M_i^+=\!\!\!\!\prod_{j=1,\, j\,\mathrm{even}}^i\!\!\!\!m_j,\,\,\,\,\,\, M_i^-=\!\!\!\!\prod_{j=1,\, j\,\mathrm{odd}}^i\!\!\!\!m_j,$$ so that $M_i=M_i^+M_i^-$. \begin{example} Take $m_i=2$ for all $i\in \mathbb{N}$. Set $I_n=\big\{\sum_{i=0}^{2n} x_{2i}M_{2i}:\, 0\leq x_i\leq 1\big\},$ with $M_i=2^i$: $$I_0=[0,1],\,\, I_1=[0,1]\cup [4,5],\,\, I_2=\{[0,1]\cup [4,5]\}\cup\{[16,17]\cup [20,21] \},\,\,\ldots $$ For $K=1$, $a_n=2^n$, and $d_n=\frac{2^{2n+1}+1}{3}$, we have $X_1=\mathcal{I}(a_n,d_n,K)$. \end{example} More generally, given a complementing pair $\mathbb{N}=X_1\oplus X_2$, take $K=m_1-1$, $a_n=\frac{M^-_{2n+1}}{m_1}$ and \begin{equation}\label{eqd} d_n=M_{2n}-\{(m_{2n-1}-1)M_{2n-2}+(m_{2n-3}-1)M_{2n-4}+\ldots +(m_3-1)M_2+(m_1-1)\}. \end{equation} With respect to these choices, the sets $I_n$ in \eqref{in} are given by $I_0=\{x_0 : \, 0\leq x_0< m_{1}\}$ and $$I_n=\big\{\sum_{i=0}^{2n} x_{2i}M_{2i}:\, 0\leq x_i< m_{i+1}\big\}.$$ Hence $X_1=\mathcal{I}(a_n,d_n,K)$. \begin{proposition} If $\mathbb{N}=X_1\oplus X_2$, then $X_1$ is not piecewise syndetic and ${\sigma}(X_1)=0$. \end{proposition} \begin{proof} To see that $X_1$ is not piecewise syndetic we only have to check that $\lim d_n = \infty$. We can rewrite \eqref{eqd} as \begin{equation*} d_n=(M_{2n}-M_{2n-1})+(M_{2n-2}-M_{2n-3})+\ldots + (M_2-M_1)+1. \end{equation*} Since $m_i\geq 2$ for all $i\geq 1$, we have $M_{2i}-M_{2i-1}\geq 1$, which means that $d_n$ is strictly increasing. \end{proof} We say that $A\subset \mathbb{N}$ is a \emph{rainbow set} with respect to a coloring $\tau:\mathbb{N}\to\mathbb{N}$ if $|\tau(A)|=|A|$. \begin{theorem} Given a complementing pair $\mathbb{N}=X_1\oplus X_2$, consider the associated infinite coloring $\tau$, as defined in the Introduction section. If \begin{equation}\label{cond}\lim_n \frac{m_{2n}}{M^-_{2(n-1)}}=0,\end{equation} then there does not exist $d\in \mathbb{N}$ and arbitrarily large sets $A$ such that $gap(A)\leq d$ and $A$ is either monochromatic or rainbow.. \end{theorem} \begin{proof} Observe that the number of colors in each interval of the form $J^k_i=[kM_{2i},(k+1)M_{2i}]$ is precisely the cardinality of the set $\big\{\sum_{j=0}^{2i-1} x_{2j+1}M_{2j+1}:\, 0\leq x_j< m_{j+1}\big\}.$ Hence, each interval $J^k_i=[kM_{2i},(k+1)M_{2i}]$ has exactly $M^+_{2i}$ colors and each color appears exactly $M^-_{2i}$ times. Let $A=\{b_1,\ldots ,b_n \}$ be a finite subset of $\mathbb{N}$ and choose $s$ minimal so that $A\subseteq J_s^{k-1}\cup J_s^k$. We have $2M_{2(s-1)}\leq b_n-b_1 \leq \mathrm{gap}(A)n.$ On the other hand, $|\tau(A)|\leq 2 M^+_{2s}$. Then \begin{equation}\label{rain} |\tau (A) |\leq \frac{\mathrm{gap}(A)|A|m_{2s}}{M^-_{2(s-1)}}.\end{equation} Hence, if $\mathrm{gap}(A)\leq d$ for some fixed $d$ and $|A|$ is large enough, from condition \eqref{cond} we get $ |\tau (A)|< |A|$, that is, we can not have arbitrarily large rainbow sequences with bounded gaps. On the other hand, $\tau$ does not admit arbitrarily large monochromatic sequences with uniformly bounded gaps because $X_1$ is not piecewise syndetic and, for each color $n_0$, the monochromatic subset $\tau^{-1}(n_0)$ is just the translation copy of $X_1$ by $n_0$. \end{proof} \begin{remark} The infinite coloring used in \cite{Br3} is the one defined by the complementing pair $\mathbb{N}=X_1\oplus X_2$ with $X_1$ the set of all finite sums $\sum_{i\,\mathrm{even}} 2^i$ and $X_2$ the set of all finite sums $\sum_{i\,\mathrm{odd}} 2^i$. In this case, $m_i=2$ for all $i\geq 1$, and condition \eqref{cond} certainly holds. \end{remark} \section{Asymptotical gap structure of positive density sets} Not surprisingly, the sequence $d_k(X)$ defined by \eqref{asgap} grows at most linearly with $k$ for sets $X$ with positive density. \begin{proposition} Let $X$ be a subset of $\mathbb{N}$ with positive lower density $\underline{\sigma}:=\underline{\sigma}(X)$. Then $d_k(X)=O(k)$ as $k\to \infty$. \end{proposition} \begin{proof} Given $0<\epsilon<\underline{\sigma}$, for all sufficiently large $n$, we must have $(\underline{\sigma}-\epsilon) n+1<|[1,n]\cap X|.$ Then the gap of $[1,n]\cap X$ is at most $n-(\underline{\sigma}-\epsilon) n.$ Hence $d_{\lceil(\underline{\sigma}-\epsilon) n\rceil+1}(X)\leq n-(\underline{\sigma}-\epsilon) n.$ Taking $k= \lceil(\underline{\sigma}-\epsilon) n\rceil+1$, we conclude that $d_k(X)=O(k)$ as $k\to\infty$. \end{proof} As the following theorem shows, this asymptotical bound is not optimal. \begin{theorem} \label{thm} Let $\varpi:[0,+\infty[\to \mathbb{R}$ be a continuous increasing function so that $\varpi(x)/x^2$ decreases with $x$. Then, if the integral \begin{equation}\label{int} \int_1^{+\infty}\frac{\varpi(x)}{x^{2}}\,dx \end{equation} diverges, any subset $X$ of $\mathbb{N}$ with $\varpi(k)=O(d_k(X))$ as $k\to\infty$ has upper density zero. \end{theorem} \begin{proof} Let $X$ be a subset of $\mathbb{N}$ with $\varpi(k)=O(d_k(X))$ and consider the increasing sequences $a_n$ and $d_n$ defined by $a_n=2^n$ and $d_n=d_{2^n}(X)$. Consider the subset $\mathcal{I}=\mathcal{I}(a_n,d_n,1)$. By Lemma \ref{iopt}, $\overline{\sigma}(X)\leq {\sigma}(\mathcal{I})$. Since $\varpi(k)=O(d_k(X))$, the series \begin{equation*} \sum_{n=1}^\infty{\big(\frac{1}{a_{n-1}}-\frac{1}{a_n}\big)}d_n=\sum_{n=1}^\infty \frac{d_{2^n}(X)}{2^n}, \end{equation*} diverges if $\sum_{n=1}^\infty \frac{\varpi(2^n)}{2^n}$ diverges. But, taking the substitution $x=2^y$, we get \begin{equation*} \int_{0}^\infty\frac{\varpi(2^{y})}{2^y}\,dy=\frac{1}{\ln 2}\int_1^{\infty} \frac{\varpi(x)}{x^{2}}\,dx. \end{equation*} Hence, by the integral convergence test, $\sum_{n=1}^\infty \frac{\varpi(2^n)}{2^n}$ diverges. By Lemma \ref{convdiv}, we conclude that ${\sigma}(\mathcal{I})=0$, and consequently $\overline{\sigma}(X)=0$. \end{proof} Conversely, \begin{theorem}\label{conv} Let $\varpi:[0,+\infty[\to \mathbb{R}$ be a continuous increasing function so that $\varpi(x)/x^2$ decreases with $x$. Then, if the integral \eqref{int} converges, there exists a subset $X$ of $\mathbb{N}$ with $\varpi(k)=O(d_k(X))$ as $k\to\infty$ and positive upper density. \end{theorem} \begin{proof} Set $a_n=2^n$, $d_n=\lceil \varpi(2^{n})\rceil$, and consider the subset $\mathcal{I}=\mathcal{I}(a_n,d_n,1)$. If the integral \eqref{int} converges, we can apply the integral convergence test, as in the proof of Theorem \ref{thm}, to conclude that the series \eqref{series} converge, and consequently ${\sigma}(\mathcal{I})>0$. Since $\varpi$ is increasing and, for $2^n0$, there exists an open interval not less than $\omega(l)$ which contains no points of $X$. For that purpose, they used sequences $u(n)$ defined by $$u(n)=g_0n+g_1\Big[\frac{n}{2}\Big]+g_2\Big[\frac{n}{2^2}\Big]+\ldots +g_p\Big[\frac{n}{2^p}\Big]+\ldots, $$ where $g_p$ is a given sequence of positive integers. For $g_0=1$ and $g_p\geq 1$, these sequences are of the form $\mathcal{I}(a_n,d_n,1)$, with $a_n=2^n$ and $d_n=g_0+g_1+\ldots+g_n$. In spite of the different notions of gap structure, the asymptotical bounds given by Theorems \ref{thm} and \ref{conv} are the same as those given by Theorems I and II in \cite{SS}. \end{remark} \section{Asymptotical gap structure and infinite colorings} Next we investigate the asymptotical growth with $k$ of the sequence $d_k(\tau)$ defined by \eqref{asgap1}. \begin{theorem} Given an infinite coloring $\tau:\mathbb{N}\to \mathbb{N}$, we have $d_k(\tau)=O(k^2)$. \end{theorem} \begin{proof} Set $\theta(n)=|\tau([1,n])|$ (the number of distinct colors occurring in the interval $[1,n]$) and define $\alpha_n=\lceil\frac{n}{\theta(n)}\rceil$. By the pigeonhole principle, there always exists a monochromatic subset $A_{\alpha_n}$ of $[1,n]$ with $\alpha_n$ elements. For each $n$, consider also a rainbow subset $B_{\theta(n)}$ of $[1,n]$ with $\theta(n)$ elements and $\theta(n)$ distinct colors. Suppose first that $\alpha_n$ is bounded: there exists $C>1$ such that $1\leq \frac{n}{\theta(n)}\leq C$ for all $n\in\mathbb{N}$. In this case, $$\mathrm{gap}(B_{\theta(n)})\leq n-(\theta(n)-1)\leq (C-1)\theta(n)+1,$$ which means that $d_k(\tau)=O(k)$. If $\alpha_n$ is not bounded, then we can assume, by taking a subsequence if necessary, that $\alpha_{n}\to\infty$. We have $$\mathrm{gap}(A_{\alpha_n})\leq n-(\alpha_n-1)\leq \lceil n/\theta(n)\rceil \theta(n)-\lceil n/\theta(n)\rceil +1.$$ Suppose that there exists $\xi>0$ such that $\xi\leq \lceil n/\theta(n)\rceil /\theta(n)$ for all $n$. In this case, $$\mathrm{gap}(A_{\alpha_n})\leq 1/\xi\lceil n/\theta(n)\rceil^2-\lceil n/\theta(n)\rceil+1,$$ and $d_k(X)=O(k^2)$. Finally, if $\lceil n/\theta(n) \rceil/\theta(n) \to 0$ (or some of its subsequences), then, for some $\eta>0$ and $n$ sufficiently large, we have $\mathrm{gap}(B_{\theta(n)})\leq \eta \theta^2(n)-\theta(n)+1,$ and consequently $d_k(X)=O(k^2)$. \end{proof} \begin{example} When $\tau $ is the infinite coloring of $\mathbb{N}$ associated to the complementing pair $\mathbb{N}=X_1\oplus X_2$, where $X_1$ is the set of all finite sums $\sum x_{2i} M_{2i}$, with $0\leq x_i< m_{i+1}$, we can give the following asymptotical bounds for $d_k(\tau)$. To simplify the discussion, assume further that, for some $m\geq 2$, we have $m_i=m$ for all $i\geq 1$. In this case, from \eqref{eqd} we can check that $$d_n=\frac{m^{2n+1}+1}{m+1}.$$ On the other hand, $|X_1\cap [0,M_{2n}]|=m^{n}+1$ and for any other interval $[\alpha,\beta]$ with $|X_1\cap [\alpha,\beta]|=m^{n}+1$ we have $$\mathrm{gap}(|X_1\cap [\alpha,\beta]|)\geq \mathrm{gap}(|X_1\cap [0,M_{2n}]|)= d_n.$$ This means that $\mathrm{gap}(A)$ grows asymptotically as fast as $|A|^2$ for monochromatic subsets $A$. From \eqref{rain} we see that $\mathrm{gap}(A)$ is asymptotically bounded below by $|A|$ for rainbow sets $A$. \end{example} \begin{thebibliography}{99} \bibitem{BHM} \newblock V. Bergelson, N. Hindman, R. McCutcheon, \newblock Notions of size and combinatorial properties of quotient sets in semigroups., \newblock \emph{Topology Proc.}, \textbf{23}, 23--60, 1998. \bibitem{Br1} \newblock T. Brown, \newblock {Locally finite semigroups.}, \newblock \emph{(Russian) Ukrain. Mat. \v{Z}.}, \textbf{20}, 732--738, 1968. \bibitem{Br2} \newblock T. Brown, \newblock {An interesting combinatorial method in the theory of locally finite semigroups.}, \newblock \emph{Pacific J. Math.}, \textbf{36}, 285--289, 1971. \bibitem{Br4} \newblock T. Brown, \newblock On the canonical version of a theorem in Ramsey theory, \newblock \emph{Combin. Probab. Comput.}, \textbf{12}, 513--514, 2003. \bibitem{Br3} \newblock T. Brown, \newblock A Partition of the Non-Negative Integers, with Applications, \newblock \emph{Integers} 5.2, Paper A02, 2005. \bibitem{EG} \newblock P. Erd\H{o}s and R. L. Graham, \newblock {Old and New Problems and Results in Combinatorial Number Theory.}, \newblock {Monographies de L'Enseignement Math\'{e}matique}, 28. Universit\'{e} de Gen\`{e}ve, 1980. \bibitem{SS} %(MR1642231) \newblock R. Salem and D. C. Spencer, \newblock{The influence of gaps on density of integers}, \newblock\emph{Duke Math. J.}, Volume 9, Number 4, 855-872, 1942. \bibitem{S} \newblock E. Szemer\'{e}di, \newblock {{On sets of integers containing no $k$ elements in arithmetic progression}}, \newblock \emph{Acta Arith.}, \textbf{27}, 199-- 245, 1975. \bibitem{Ti} \newblock R. Tijdeman, \newblock {Decomposition of the integers as a direct sum of two subsets}, \newblock Number theory (Paris, 1992-1993), London Math. Soc. Lecture Note Ser. \textbf{215} (1995), Cambridge Univ. Press, 261-- 276. \end{thebibliography} \end{document}