# 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)$.

-
@Fedor: wonderful, exactly what I was looking for. Do you think that this bound is tight? – Victor Miller Nov 16 '10 at 20:41
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
@Fedor: Yes. I like the statement. Without loss of generality, we can restrict our attention to finite such sets P. Then we can work modulo their least common multiple, transforming the original statement into a very combinatorial statement about finite abelian groups. I don't have any good ideas about how to prove it, though... – Sergey Norin Nov 16 '10 at 23:37

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) ).$$

-