Close Menu
Thursday, January 22
Math

Rogers’ theorem on sieving | What’s new

adminBy No Comments5 Mins Read1 Views
Rogers’ theorem on sieving | What’s new


A basic problem in sieve theory is to understand what happens when we start with the integers {{\bf Z}} (or some subinterval of the integers) and remove some congruence classes {a_i \pmod{q_i}} for various moduli {q_i}. Here we shall concern ourselves with the simple setting where we are sieving the entire integers rather than an interval, and are only removing a finite number of congruence classes {a_1 \pmod{q_1}, \ldots, a_k \pmod{q_k}}. In this case, the set of integers that remain after the sieving is periodic with period {Q = \mathrm{lcm}(q_1,\dots,q_k)}, so one work without loss of generality in the cyclic group {{\bf Z}/Q{\bf Z}}. One can then ask: what is the density of the sieved set

\displaystyle \{ n \in {\bf Z}/Q{\bf Z}: n \neq a_i \hbox{ mod } q_i \hbox{ for all } i=1,\ldots,k \}? \ \ \ \ \ (1)


 If the {q_i} were all coprime, then it is easy to see from the Chinese remainder theorem that the density is given by the product

\displaystyle \prod_{i=1}^k \left(1 - \frac{1}{q_i}\right).

However, when the {q_i} are not coprime, the situation is more complicated. One can use the inclusion-exclusion formula to get a complicated expression for the density, but it is not easy to work with. Sieve theory also supplies one with various useful upper and lower bounds (starting with the classical Bonferroni inequalities), but do not give exact formulae.

In this blog post I would like to note one simple fact, due to Rogers, that one can say about this problem:

Theorem 1 (Rogers’ theorem) For fixed {q_1,\dots,q_k}, the density of the sieved set is maximized when all the {a_i} vanish. Thus,

\displaystyle |\{ n \in {\bf Z}/Q{\bf Z}: n \neq a_i \hbox{ mod } q_i \hbox{ for all } i=1,\ldots,k \}|

\displaystyle \leq |\{ n \in {\bf Z}/Q{\bf Z}: n \neq 0 \hbox{ mod } q_i \hbox{ for all } i=1,\ldots,k \}|.

Example 2 If one sieves out {1 \pmod{2}}, {1 \pmod{3}}, and {2 \pmod{6}}, then only {0 \pmod{6}} remains, giving a density of {1/6}. On the other hand, if one sieves out {0 \pmod{2}}, {0 \pmod{3}}, and {0 \pmod{6}}, then the remaining elements are {1} and {5 \pmod{6}}, giving the larger density of {2/6}.

This theorem is somewhat obscure: its only appearance in print is in pages 242-244 of this 1966 text of Halberstam and Roth, where the authors write in a footnote that the result is “unpublished; communicated to the authors by Professor Rogers”. I have only been able to find it cited in three places in the literature: in this 1996 paper of Lewis, in this 2007 paper of Filaseta, Ford, Konyagin, Pomerance, and Yu (where they credit Tenenbaum for bringing the reference to their attention), and is also briefly mentioned in this 2008 paper of Ford. As far as I can tell, the result is not available online, which could explain why it is rarely cited (and also not known to AI tools). This became relevant recently with regards to Erdös problem 281, posed by Erdös and Graham in 1980, which was solved recently by Neel Somani through an AI query by an elegant ergodic theory argument. However, shortly after this solution was located, it was discovered by KoishiChan that Rogers’ theorem reduced this problem immediately to a very old result of Davenport and Erdös from 1936. Apparently, Rogers’ theorem was so obscure that even Erdös was unaware of it when posing the problem!

Modern readers may see some similarities between Rogers’ theorem and various rearrangement or monotonicity inequalites, suggesting that the result may be proven by some sort of “symmetrization” or “compression” method. This is indeed the case, and is basically Rogers’ original proof. We can modernize a bit as follows. Firstly, we can abstract {{\bf Z}/Q{\bf Z}} into a finite cyclic abelian group {G}, with residue classes now becoming cosets of various subgroups of {G}. We can take complements and restate Rogers’ theorem as follows:

Theorem 3 (Rogers’ theorem, again) Let {a_1+H_1, \dots, a_k+H_k} be cosets of a finite cyclic abelian group {G}. Then

\displaystyle |\bigcup_{j=1}^k a_j + H_j| \geq |\bigcup_{j=1}^k H_j|.

Example 4 Take {G = {\bf Z}/6{\bf Z}}, {H_1 = 2{\bf Z}/6{\bf Z}}, {H_2 = 3{\bf Z}/6{\bf Z}}, and {H_3 = 6{\bf Z}/6{\bf Z}}. Then the cosets {1 + H_1}, {1 + H_2}, and {2 + H_3} cover the residues {\{1,2,3,4,5\}}, with a cardinality of {5}; but the subgroups {H_1,H_2,H_3} cover the residues {\{0,2,3,4\}}, having the smaller cardinality of {4}.

Intuitively: “sliding” the cosets {a_i+H_i} together reduces the total amount of space that these cosets occupy. As pointed out in comments, the requirement of cyclicity is crucial; four lines in a finite affine plane already suffice to be a counterexample otherwise.

By factoring the cyclic group into p-groups, Rogers’ theorem is an immediate consequence of two observations:

Theorem 5 (Rogers’ theorem for cyclic groups of prime order) Rogers’ theorem holds when {G = {\bf Z}/p^n {\bf Z}} for some prime power {p^n}.

Theorem 6 (Rogers’ theorem preserved under products) If Rogers’ theorem holds for two finite abelian groups {G_1, G_2} of coprime orders, then it also holds for the product {G_1 \times G_2}.

The case of cyclic groups of prime order is trivial, because the subgroups of {G} are totally ordered. In this case {\bigcup_{j=1}^k H_j} is simply the largest of the {H_j}, which has the same size as {a_j + H_j} and thus has lesser or equal cardinality to {\bigcup_{j=1}^k a_j + H_j}.

The preservation of Rogers’ theorem under products is also routine to verify. By the coprime orders of {G_1,G_2} and standard group theoretic arguments (e.g., Goursat’s lemma, the Schur–Zassenhaus theorem, or the classification of finite abelian groups), one can see that any subgroup {H_j} of {G_1 \times G_2} splits as a direct product {H_j = H_{j,1} \times H_{j,2}} of subgroups of {G_1,G_2} respectively, so the cosets {a_j + H_j} also split as

\displaystyle a_j + H_j = (a_{j,1} + H_{j,1}) \times (a_{j,2} + H_{j,2}).

Applying Rogers’ theorem for {G_2} to each “vertical slice” of {G_1 \times G_2} and summing, we see that

\displaystyle |\bigcup_{j=1}^k (a_{j,1} + H_{j,1}) \times (a_{j,2} + H_{j,2})| \geq |\bigcup_{j=1}^k (a_{j,1} + H_{j,1}) \times H_{j,2}|

and then applying Rogers’ theorem for {G_1} to each “horizontal slice” of {G_1 \times G_2} and summing, we obtain

\displaystyle |\bigcup_{j=1}^k (a_{j,1} + H_{j,1}) \times H_{j,2}| \geq |\bigcup_{j=1}^k H_{j,1} \times H_{j,2}|.

Combining the two inequalities, we obtain the claim.



Source link

Share.
thanhphuchoang09

Related Posts

Add A Comment
Leave A Reply