# Density of congruence classes covered by a set

Thinking about the question Four polynomials representing all integers modulo m lead me to the following complementary question:

If $S$ is a set of positive integers, say that a positive integer $m$ is covered by $S$ if every congruence class $\bmod m$ has a representative in $S$. Denote by $C(S)$ the set of positive integers covered by $S$. If $x>0$ let $S(x) = \{ k \in S : k \le x \}$ and the lower density of $S$, $\ell(S) := \lim \inf_{x \rightarrow \infty} |S(x)|/x$. My question: is there a non-trivial lower bound on $\ell(C(S))$ in terms of $\ell(S)$? That is, is there a continuous function $f : [0,1] \rightarrow [0,1]$, not identically 0, such that $\ell(C(S)) \ge f(\ell(S))$.

The set in the question I referred to has density 0, so my question wouldn't apply to it. However, I wondered if there were a simple argument in the case of positive lower density. This has the smell of the kind of question that Erdos would ask, so I wouldn't be surprised to see it there.

• A couple of examples: for $S$ being the set of primes, $C(S)=S$. The obvious construction reveals that there are arbitrarily thin $S$ with $C(S)$ being all natural numbers. Also, $C(evens)=odds$. For $S=0\mod m$, we have $C(S)$ being the set of numbers relatively prime to $m$. This last example is most relevant to the question, but doesn't answer it. – Kevin O'Bryant Nov 16 '10 at 17:04
• To avoid trivialities, we should insist that $f$ be continuous, $f(0)=0,f(1)=1$. – Kevin O'Bryant Nov 16 '10 at 18:33
• @Kevin: if S is the set of primes, don't you get C(S) = N? – Qiaochu Yuan Nov 16 '10 at 19:52
• @Qiaochu: no, primes do not give remainder 0 modulo any composite number – Fedor Petrov Nov 16 '10 at 20:09

Denote by $P$ the set of prime powers not covered by $S$ (for each prime $p$, take only the smallest non-covered its power). If $\sum_{x\in P} 1/x=+\infty$, then $\prod_{x\in P} (1-1/x)$ is 0, so the product over some finite subset is arbitrarily small. But this product is a density of numbers without forbidden remainders modulo respective prime powers. So, $S$ has density 0. A contradiction. Hence $a=\prod_{x\in P} (1-1/x)$ is positive and $\ell(S)\leq a$. But then complement of $C(S)$ is the set of numbers divisible by at least one element of $P$. Density of such numbers equals $1-a$ (this is rather technical, but standard). So, we get that $\ell(C(S))\geq \ell(S)$.
• well, if $S$ is the set of numbers not divisible by any element of $P$, then $S=C(S)$ – Fedor Petrov Nov 16 '10 at 21:18
• Does $C(S)$ have to consist only of numbers divisible by an element of $P$? I think it is possible for primes $p_1$ and $p_2$ to be covered by $S$, while the product $p_1p_2$ is not (e.g. $S$ is the set of all integers not congruent to $5$ modulo $6$). – Sergey Norin Nov 16 '10 at 22:35
• ops! You are completely right, that's a stupid mistake. Maybe, we may fix it by proving that for any set of mutually non-divisible by others set $P$, the density of numbers, divisible by at least one element of $P$, is not more then then the density of union $\cup_{x\in P} x\mathbb{N}+r(x)$ for arbitrary different shifts $r$'s. it looks like a nice statement at least – Fedor Petrov Nov 16 '10 at 23:21
This obviously isn't what was intended, but satisfies the letter of the question. If $S$ has density 1, then it must contain arbitrarily long intervals. Therefore, $C(S)={\mathbb{N}}$. I set $f(x)=[x=1]$ (using Iverson's notation), and we have:
$$\ell(C(S)) \geq f( \ell (S) ).$$