Examples of Sets with Positive Upper Density

Question

While reading the statement of Roth's theorem I started asking myself what are examples of sets of positive upper density? It's not hard to come up with a few:

• Flip a coin with probability $\mathbb{P}(H) = p < 1$ and take all the heads
• Consider $\{ n : \{ n \theta\} > 0.001$ where $\theta$ is an irrational number

While searching the OEIS I only found a few more:

• $n$ with a prime factor such that $p > \sqrt{n}$ has density $\log 2$
• $n = p + 2^k$ where $k \geq 1$ and $p$ is prime.

Then there are square-free numbers and $\{ n : n^2 + 1 \text{ is square-free} \}$.

I have been looking through various sources... such as Roth's book who writes very abstractly. In a sense, chosen any correctly-chosen set can have positive upper density, but are there any good examples that you are aware of?

Erdos may have come up with a few. I considered making my coin-flip example deterministic.

Answer 1

The Birkhoff ergodic theorem produces many integer sets of positive upper density. Given a probability space $(X, \mu)$, a transformation $T : X \rightarrow X$ preserving $\mu$, and some measurable set $A \subset X$, we have the convergence for almost all $x \in X$, $$ {1\over N} Card\{k< N \mid T^k(x)\in A\} \rightarrow E({\bf 1}_A \mid {\cal I})(x) $$ where $E({\bf 1}_A \mid {\cal I})$ is the conditional expectation of the indicatrix function of $A$ with respect to the $\sigma$-algebra ${\cal I}$ of $T$-invariant sets. That function is positive on $A$ for almost all $x$. So the set of $k$ for which $T^k(x)$ belongs to $A$ has positive upper density for almost all $x\in A$. This is a strengthening of the Poincaré recurrence theorem.

If $T$ happens to be uniquely ergodic and $\mu$ is of full support, as in the example of an irrational rotation $x\mapsto x+\theta$ on the circle, the convergence holds for all x, so this is a bit more explicit.

Answer 2

Converging sieves: Let $q_i$ be a sequence of integers with $\sum\frac{1}{q_i}<\infty$, and pick for each $i$ an integer $a_i$ within a finite set $\mathcal{A}$. Then the set of integers $n$ such that $n\not\equiv a_i\pmod{q_i}$ has positive density. Most examples involve coprime integers $q_i$, an example where the $q_i$ have large common divisors is the set of integers $n$ such that every group of order $n$ is solvable.

Sets of integers defined by values of arithmetic functions: For every $c\in(0,1)$ the set $\{n:\varphi(n)<cn\}$ has positive density, and for every $c>1$ the set $\{n:\sigma(n)<cn\}$ has positive density. Many other examples of this type arise from the Erdos-Kac-theorem.

Logical limit laws: If $\varphi$ is a statement in the unary second order language of groups, then the set of all $n$, such that all abelian groups of order $n$ satisfy $\varphi$ has a Dirichlet density, which is quite often strictly between 0 and 1. Other examples can be deduced from the examples in Burris' book "Number theoretic densities and logical limit laws".