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.

  • $\begingroup$ 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? $\endgroup$ – Stanley Yao Xiao Jul 21 '16 at 18:45
  • $\begingroup$ 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}$. $\endgroup$ – john mangual Jul 21 '16 at 18:51
  • 1
    $\begingroup$ 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. $\endgroup$ – Anthony Quas Jul 21 '16 at 19:40

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.

| cite | improve this answer | |
  • $\begingroup$ this is what I had in mind. and of course it's tied to Furstenberg's proof $\endgroup$ – john mangual Jul 21 '16 at 18:52
  • $\begingroup$ 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$. $\endgroup$ – 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".

| cite | improve this answer | |
  • $\begingroup$ Right. Changed it. $\endgroup$ – Jan-Christoph Schlage-Puchta Jul 25 '16 at 14:40
  • $\begingroup$ Thanks for clarifying the condition on the reciprocal steps. $\endgroup$ – kodlu Jul 25 '16 at 22:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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