# Density of a set of natural numbers whose differences are not bounded.

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

• 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

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 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

• 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.