# Examples of Sets with Positive Upper Density

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.

• Are you looking for subsets of positive integers? I assume you also want examples where the upper density is positive but the density is not defined? – Stanley Yao Xiao Jul 21 '16 at 18:45
• my apologies, yes $A \subseteq \mathbb{Z}$. I mean let $f: \mathbb{R} \to [-1,1]$ be any reasonable bounded oscillating function, and chose the Bohr set of $\{f \geq 0\} \cap \mathbb{Z}$. – john mangual Jul 21 '16 at 18:51
• Here's another nice example: the set of numbers that have an even number of 1's in their binary expansion. This is related to the (Prouhet)-Thue-Morse sequence. – Anthony Quas Jul 21 '16 at 19:40

## 2 Answers

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.

• this is what I had in mind. and of course it's tied to Furstenberg's proof – john mangual Jul 21 '16 at 18:52
• A remark on the circle rotation example (and uniquely ergodic topological systems in general): for everywhere convergence to hold, the boundary of $A$ must have measure $0$. – John Griesmer Jul 30 '16 at 17:48

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

• Right. Changed it. – Jan-Christoph Schlage-Puchta Jul 25 '16 at 14:40
• Thanks for clarifying the condition on the reciprocal steps. – kodlu Jul 25 '16 at 22:50