Skip to main content
added 3 characters in body
Source Link
Fedor Petrov
  • 108.9k
  • 9
  • 264
  • 459

Denote by $P$ the set of prime powers not covered by $S$ (for eaceach prime $p$, take only the smallessmallest 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 remainersremainders 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)$.

Denote by $P$ the set of prime powers not covered by $S$ (for eac prime $p$, take only the smalles 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 remainers 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)$.

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

Source Link
Fedor Petrov
  • 108.9k
  • 9
  • 264
  • 459

Denote by $P$ the set of prime powers not covered by $S$ (for eac prime $p$, take only the smalles 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 remainers 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)$.