Set of Banach upper density zero

Question

For any set $A$ of natural numbers, the Banach upper density is defined as $$b^*(A)=\lim_{n\to\infty}\max_{m\geq0}\frac{|A\cap [m+1,m+n]|}{n}.$$ Does a set $A$ that has arbitrarily long arithmetic progression have positive Banach density?

Answer 1

Well, I tried to prove it and couldn't really see why it should be true, so below is my attempt at a counter-example. I think some of the details might be missing, but I hope the logic is sound:

1. Let $A_2 = \{1,3\}$

2. Let $A_3 = \{1,4,7\}$

   $\vdots$

3. Let $A_n = \{1,n+1,\ldots,(n-1)n + 1\}$

Furthermore, let $k_n = \sum_{m < n} m^2$

Now let $A = \bigcup_{l=1}^\infty \{k_l + x | x \in A_k\}$. As requested, $A$ contains arbitrarily long arithmetic progressions.

• $\frac{|A \cap [k_l,k_{l+1})|}{k_{l+1} - k_l} = \frac{l}{l^2}$.

And composing this across several intervals we have

• $\frac{|A\cap [1,k_{m+1})|}{k_{m+1}} = \frac{\sum_{l=1}^m l}{\sum_{l=1}^m l^2} = \frac{m(m+1)/2}{m(m+1)(2m+1)/6} = \frac{3}{2m + 1}$

And so $\lim_{m\to\infty}\frac{|A\cap [1,k_{m+1})|}{k_{m+1}} = 0$.

Answer 2

A "famous" counterexample is the set of primes, which have Banach density 0. Green and Tao showed that the primes contain arbitrarily long arithmetic progressions.

However, as indicated by John C's answer, ad hoc examples are much easier to come by. In his answer, the set $A$ is a union of arithmetic progressions of length $n$, common difference $n$, and very large initial term (relative to $n$). Although the final calculation only shows upper natural density $0$, not upper Banach (i.e., uniform) density $0$.

Another method is to just take the set $A$ to be a union of arithmetic progressions of divergent length, but whose common difference is very large with respect to its length.

For example, given $n>0$, let $A_n=\{kn^n:1\leq k\leq n\}$ (an arithmetic progression of length $n$ and common difference $n^n$). Let $A=\bigcup_{n>0} A_n$. Then we claim $A_n$ has Banach density $0$.

Proof: It suffices to fix intervals $I_n=[a_n,b_n]$ in $\mathbb{N}$, with $\lim_{n\to\infty}b_n-a_n=\infty$, and show $\lim_{n\to\infty}\frac{|A\cap I_n|}{b_n-a_n+1}=0$. By passing to a subsequence if necessary, we may assume without loss of generality that $|A\cap I_n|\geq 3$ for all $n$. So for each $n$, we may choose $k_n>0$ maximal such that $mk_n^{k_n},(m+1)k_n^{k_n}\in A\cap I_n$ for some $1\leq m<k_n$. Note that $(k_n)$ diverges since $(b_n)$ diverges.

Now, since $\max A_{k_n}<\min A_{k_n+1}$, we have $$ A\cap I_n\subseteq\bigcup_{t=1}^{k_n} A_t\cup \{\min A_{k_n+1}\}, $$ which means $|A\cap I_n|\leq 1+\sum_{t=1}^{k_n}t\leq k_n^2+1$. On the other hand, $a_n\leq mk_n^{k_n}<(m+1)k_n^{k_n}\leq b_n$, and so $b_n-a_n\geq k_n^{k_n}$. Altogether $$ \lim_{n\to\infty}\frac{|A\cap I_n|}{b_n-a_n+1}\leq \lim_{n\to\infty}\frac{k_n^2+1}{k_n^{k_n}}=0. $$

The only reason the function $n^n$ was chosen was to force $\max A_n<\min A_{n+1}$. Instead one could use some other increasing function $f\colon\mathbb{N}\to\mathbb{N}$ in the definition of $A_n$, and choose an infinite subsequence $(A_{n_i})$ of $(A_n)$ with $\max A_{n_i}<\min A_{n_{i+1}}$. Then, as long as $\lim_{n\to\infty}\frac{n^2}{f(n)}=0$, the rest of the proof is the same.