Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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,


share|improve this question
Regarding your first question, I think it's false : take an infinite sequence of consecutive integers, with only very rare jumps. –  François Brunault May 27 '11 at 13:59
A minor modification of Francois Brunault's solution gives you a partition of $\mathbb N$ into two pieces both of which have unbounded $d_n$'s; where one piece has a big gap to make its $d_n$ big, the other has a run of consecutive 1's. That prevents any non-trivial mean (invariant or not) from being 0 on all such sets. (I suspect that number theorists will object to the "number theory" tag.) –  Andreas Blass May 27 '11 at 14:10
Possible counterexample: Choose a sparse enough set of primes with sum of reciprocals $<1$ and then consider the integers which are not divisible by any of these primes. –  Gjergji Zaimi May 27 '11 at 14:10
I believe that the condition that a set has arbitrary large gaps is equivalent to $\underline u(A)=0$, where $\underline u(A)$ stands for lower uniform density (a.k.a. lower Banach density). Relation to asymptotic density: $\underline u(A)\le \underline d(A) \le \overline d(A) \le \overline u(A)$. –  Martin Sleziak May 27 '11 at 14:22
As an addendum to my previous comment: $\overline u(A)=0$ is equivalent to the condition that all shift-invariant means have the value zero on $A$. (The upper Banach density $\overline u(A)$ is the supremum/maximum of the values of shift-invariant means $\mu(A)$.) –  Martin Sleziak May 27 '11 at 14:28

2 Answers 2

up vote 6 down vote accepted

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 Invariant means on the integers 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.)

EDIT: The question whether the result mentioned in preceding paragraph holds is now posted on MO as a separate question: On the independence of lower and upper asymptotic and Banach 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

share|improve this answer
many many thanks!! I am going to read everything right away! –  Valerio Capraro May 27 '11 at 18:06
I think Luca (and others) is the author of a recent (last 10 years) paper that proves that "for any choice of $0\leq a \leq b \leq c \leq d \leq 1$ ...". I just sat in a talk of Renling Jin's (perhaps joint work with Grekos) where he announced a simplification and extension of this (several other measures involved also simultaneously). –  Kevin O'Bryant May 29 '11 at 22:48
@Kevin: I tried to google a little, but I only found results concerning asymptotitc and logarithmic density. Luca-Pomerance-Porubsky: Sets with prescribed arithmetic densities math.dartmouth.edu/~carlp/LuPoPor08-2.pdf Luca-Porubsky: On asymptotic and logaritmic densities sav.sk/journals/uploads/0131154306POLU06.ps Do you happen to have a reference for that results? (Maybe you have slides or notes from the talk...) –  Martin Sleziak Jun 2 '11 at 5:56

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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.