A nice result on arithmetic progressions

Let \mathbb N_0 denote the set of the non-negative integers. For a subset S\subseteq\mathbb N_0, we can define the ‘counting function’

\pi_S(x):=|\{n\in\mathbb N_0\cap S:n\le x\}|

i.e. \pi_S(x) is the number of elements in S that are at most x. Then we can define the (asymptotic) density of S as

\displaystyle \delta(S):=\lim_{x\to\infty}\frac{\pi_S(x)}{x}

when this limit exists.

For example, the set of the even (resp. odd) numbers has density 1/2. More generally, any arithmetic progression a+d\mathbb N_0:=\{a+dn:n\in\mathbb N_0\} has density 1/d. Another example is the set of prime numbers, which has density 0 by the prime number theorem. From this it also follows that the set of composite numbers has density 1.

Theorem. If a finite union of arithmetic progressions of positive integers has density 1, then it contains all sufficiently large positive integers.

Proof. Let

\displaystyle A=\bigcup_{i=1}^k(a_i+d_i\mathbb N_0)

be a finite union of arithmetic progressions such that \delta(A)=1. Note that (this is the main trick) we can write:

\displaystyle A=\bigcup_{i=1}^k(a_i+d_i\mathbb N_0)=\bigcup_{j=1}^l(b_i+d\mathbb N_0)

for some b_1,\dots,b_l, where d is the least common multiple of d_1,\dots,d_k.

Why can we do this? Consider for example (1+2\mathbb N_0)\cup(2+3\mathbb N_0). We can write this as

\displaystyle \underbrace{(1+6\mathbb N_0)\cup (3+6\mathbb N_0)\cup (5+6\mathbb N_0)}_{1+2\mathbb N_0}\cup \underbrace{(2+6\mathbb N_0)\cup (5+6\mathbb N_0)}_{2+3\mathbb N_0}

\displaystyle =(1+6\mathbb N_0)\cup (2+6\mathbb N_0)\cup (3+6\mathbb N_0)\cup (5+6\mathbb N_0)

And this idea works for any finite union of arithmetic progressions.

It is then clear that \{b_1,\dots,b_l\} has to be a complete set of residues modulo d, because otherwise A would have density strictly less than 1. Therefore A has to contain all positive integers \ge\max\{b_1,\dots,b_l\}. \square

We get the following nice corollary:

Corollary. The set of all composite numbers cannot be expressed as a finite union of arithmetic progressions of positive integers.

Proof. Otherwise by the above theorem all sufficiently large positive integers would be composite, contradicting the fact that there are infinitely many primes. \square

Advertisements

Leave a comment

Filed under Combinatorics, Number theory

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s