9
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$
    – Kevin O'Bryant
    Commented Nov 16, 2010 at 17:04
  • 1
    $\begingroup$ To avoid trivialities, we should insist that $f$ be continuous, $f(0)=0,f(1)=1$. $\endgroup$
    – Kevin O'Bryant
    Commented Nov 16, 2010 at 18:33
  • $\begingroup$ @Kevin: if S is the set of primes, don't you get C(S) = N? $\endgroup$
    – Qiaochu Yuan
    Commented Nov 16, 2010 at 19:52
  • $\begingroup$ @Qiaochu: no, primes do not give remainder 0 modulo any composite number $\endgroup$
    – Fedor Petrov
    Commented Nov 16, 2010 at 20:09

2 Answers 2

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$
8
  • $\begingroup$ @Fedor: wonderful, exactly what I was looking for. Do you think that this bound is tight? $\endgroup$
    – Victor Miller
    Commented Nov 16, 2010 at 20:41
  • 1
    $\begingroup$ well, if $S$ is the set of numbers not divisible by any element of $P$, then $S=C(S)$ $\endgroup$
    – Fedor Petrov
    Commented Nov 16, 2010 at 21:18
  • 2
    $\begingroup$ 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$). $\endgroup$
    – Sergey Norin
    Commented Nov 16, 2010 at 22:35
  • $\begingroup$ 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 $\endgroup$
    – Fedor Petrov
    Commented Nov 16, 2010 at 23:21
  • $\begingroup$ @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... $\endgroup$
    – Sergey Norin
    Commented Nov 16, 2010 at 23:37
3
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .