\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^n<k<2^{n+1}$, we have
  $d_k(\mathcal{I})=d_{2^{n+1}}(\mathcal{I})=d_{n+1},$
  it is clear that   $\varpi(k)=O(d_k(\mathcal{I}))$. Set  $X=\mathcal{I}$, and we are done.
\end{proof}

\begin{remark}
In \cite{SS}, R. Salem and D.C. Spencer studied the influence of gaps in the density of integer subsets. However, a different notion of gap structure is considered there. More precisely, given an positive increasing function $\omega $ of the real nonnegative variable $x$, they were concerned with subsets $X$ of $\mathbb{N}$ satisfying the following property: for any closed interval $[a,a+l]$, with $a\geq 0$ and $l>0$, 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}
