Question

I guess this is quite standard and probably easy for experts or young lovers of number theory.

For $A\subseteq\mathbb N$, denote by $d^+(A)$ its upper density, which is $$ d^+(A)=\lim\sup_{n\rightarrow\infty}\frac{|A\cap[1,n]|}{n} $$ Now let $A=(a_n)$ be an increasing sequence of natural numbers and let $d_n$ be the $n$-th difference $d_n=a_{n}-a_{n-1}$.

Question: Suppose that $d_n$ is not bounded, is it true that $d^+(A)=0$?

More generally: if $d_n$ is not bounded, is it true that any (additive) invariant mean on $\mathbb N$ takes value $0$ over $A$?

Thanks in advance,

Valerio

Answer 1

Basic definitions:

Upper and lower asymptotic density (a.k.a. natural density):

$$\overline d(A)=\limsup \frac{A(n)}n$$

$$\underline d(A)=\liminf \frac{A(n)}n$$

Upper and lower uniform density (a.k.a. Banach density):

$$\overline u(A)=\lim_{s\to\infty} \max_{t\ge 0}\frac{A(t+1,t+s)}{s}$$

$$\underline u(A)=\lim_{s\to\infty} \min_{t\ge 0}\frac{A(t+1,t+s)}{s}$$

where $A(m,k)=|A\cap\{m,m+1,\dots,k\}|$ and $A(n)=A(1,n)$.

Note that $\underline d(\mathbb N\setminus A)=1-\overline d(A)$ and $\underline u(\mathbb N\setminus A)=1-\overline u(A)$.

It is known that $\underline u(A)\le \underline d(A) \le \overline d(A) \le \overline u(A)$, see e.g. [GLS].

---

The condition that $d_n$ is unbounded is equivalent to $\underline u(A)=0$.

(If $d_n$ is unbounded that we can found arbitrarily large $s$ with $A(t+1,t+s)=0$. On the other hand, if $d_n\le M$, then $A(t+1,t+s) \ge \left\lfloor\frac{s}M\right\rfloor$ and $\underline u(A)\ge \frac 1M$.)

It is known that $\overline u(A)=\sup\{\mu(A); \mu\text{ is a shift-invariant mean on }\mathbb N\}$. The proof of this fact can be found in [B]. (EDIT: Now I realized that you have seen this result in an answer to another your question http://mathoverflow.net/questions/60897/invariant-means-on-the-integers/65655#65655 Both [B] and this answer invariant concern invariant means on $\mathbb Z$ and not $\mathbb N$, but this should not make much difference.)

---

Knowing all of this, you in fact ask whether $\underline u(A)=0$ implies $\overline d(A)=0$ or even $\overline u(A)=0$. Many counterexamples can be found. Just one of them: For the set

$$A=\mathbb N\setminus \bigcup_{k=1}^\infty \{10^k+1,\dots,10^k+k\}$$

we get $\underline u(A)=0$ and $\underline d(A)=\overline d(A)=\overline u(A)=1$.

(If I remember correctly, I have seen the result that for any choice of $0\le a \le b \le c \le d\le 1$ there exists a set $A$ such that the values of $\underline u(A)$, $\underline d(A)$, $\overline d(A)$, $\overline u(A)$ are $a$, $b$, $c$ and $d$, respectively; but I might be mistaken and I cannot find any reference right now. Maybe I mixed it up with a similar result for some other type of densities.)

---

Perhaps I should mention that several equivalent definitions of Banach/uniform density appear in the literature. They are compared e.g. in [GTT]. (E.g. [B] works with a different - but equivalent - definition.)

Some references to papers where this notion was studied under the name uniform density are given in [GLS]. If I am not mistaken, the term Banach density was coined by Furstenberg [F].

[B] Mathias Beiglbock: An ultrafilter approach to Jin’s Theorem http://www.mat.univie.ac.at/~mathias/UltraJin_final.pdf

[F] H. Furstenberg. Recurrence in ergodic theory and combinatorial number theory. Princeton University Press, Princeton, 1981.

[GLS] Z. Gáliková, B. Lászlo and T. Šalát: Remarks on uniform density of sets of integers http://www.emis.ams.org/journals/AMI/2002/acta2002-galikova-laszlo-salat.pdf

[GTT] Georges Grekos, Vladimír Toma and Jana Tomanová. A note on uniform or Banach density. http://ambp.cedram.org/ambp-bin/fitem?id=AMBP_2010__17_1_153_0

Answer 2

Remove from $\mathbb N$ the subset $\cup_{n=1}^\infty \lbrace n!,n!+1,\dots,n!+n\rbrace$. The result has density $1$ and arbitrarily large gaps.