MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 3 down vote accepted

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

share|cite|improve this answer
@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) ).$$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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