3
$\begingroup$

A traditional sieve gives a bound on the number of integers $n$ in an interval (say $I=[0,N]$) such that $$n\not\in S_p \mod p$$ for every prime $p$ in a set $\mathcal{P}$, where $S_p\subset \mathbb{Z}/p\mathbb{Z}$.

What happens if instead we are given a set $\mathcal{M}$ of composite moduli, and asked to give an upper bound on the number of integers $n$ in $I$ such that $$n\not\in S_m \mod m\;\;\; \forall m\in \mathcal{M},$$ where $S_m\subset \mathbb{Z}/m\mathbb{Z}$? Is there any literature on the matter? Note the elements of $\mathcal{M}$ need not be pairwise coprime.

$\endgroup$
4
  • $\begingroup$ If the set is finite and not redundant (for each m there is number sieved only by m), the standard elementary arguments should work on a large scale just like with primes. Remember to redefine Eulers phi so that phi(m)=m-1. Were you thinking about short intervals? Gerhard "Jacobsthal May Play A Role" Paseman, 2020.07.06. $\endgroup$ Jul 6, 2020 at 16:05
  • $\begingroup$ Oops. There is a twist. One does have to consider common divisors of the m_i. I will think further on this. I have no references at present for this problem for composite moduli. Gerhard "Found More To Throw Out" Paseman, 2020.07.06. $\endgroup$ Jul 6, 2020 at 16:12
  • $\begingroup$ Is $S_p$ the set of integers not divisible by $p$? $\endgroup$
    – kodlu
    Jul 7, 2020 at 0:01
  • 1
    $\begingroup$ No, it's just the set of excluded classes. Call it $\Omega_p$ if you prefer. $\endgroup$ Jul 7, 2020 at 7:07

1 Answer 1

3
$\begingroup$
  1. A. Sarközy, A note on the arithmetic form of the large sieve, Sudia Sci Math Hungarica 27, 1992, 83--95

covers the literature until then (there are some later results, adapting this as needed.)

  1. I. Ruzsa, On the small sieve. II. Sifting by composite numbers Journal of Number Theory 14 (2), 1982, 260--268
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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