science

Larger sieve

Larger sieve is a science topic covered in the lgStudy science library. This page brings together a partial reference excerpt, illustrations, worked examples, real-world applications and a short study plan, so you can understand Larger sieve rather than just read about it. In short: In number theory, the larger sieve is a sieve invented by Patrick X. Gallagher.

Key takeaways

Larger sieve belongs to science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Larger sieve to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Larger sieve from memory before moving on to harder problems.

Reference excerpt

In number theory, the larger sieve is a sieve invented by Patrick X. Gallagher. The name denotes a heightening of the large sieve. Combinatorial sieves like the Selberg sieve are strongest, when only a few residue classes are removed, while the term large sieve means that this sieve can take advantage of the removal of a large number of up to half of all residue classes. The larger sieve can exploit the deletion of an arbitrary number of classes.

Statement Suppose that S {\displaystyle {\mathcal {S}}} is a set of prime powers, N an integer, A {\displaystyle {\mathcal {A}}} a set of integers in the interval [1, N], such that for q ∈ S {\displaystyle q\in {\mathcal {S}}} there are at most g ( q ) {\displaystyle g(q)} residue classes modulo q {\displaystyle q} , which contain elements of A {\displaystyle {\mathcal {A}}} . Then we have

| A | ≤ ∑ q ∈ S Λ ( q ) − log ⁡ N ∑ q ∈ S Λ ( q ) g ( q ) − log ⁡ N , {\displaystyle |{\mathcal {A}}|\leq {\frac {\sum _{q\in {\mathcal {S}}}\Lambda (q)-\log N}{\sum _{q\in {\mathcal {S}}}{\frac {\Lambda (q)}{g(q)}}-\log N}},}

provided the denominator on the right is positive.

Applications A typical application is the following result, for which the large sieve fails (specifically for θ > 1 2 {\displaystyle \theta >{\frac {1}{2}}} ), due to Gallagher:

If the number of excluded residue classes modulo p {\displaystyle p} varies with p {\displaystyle p} , then the larger sieve is often combined with the large sieve. The larger sieve is applied with the set S {\displaystyle {\mathcal {S}}} above defined to be the set of primes for which many residue classes are removed, while the large sieve is used to obtain information using the primes outside S {\displaystyle {\mathcal {S}}} .

Notes

References Gallagher, Patrick (1971). "A larger sieve". Acta Arithmetica. 18: 77–81. doi:10.4064/aa-18-1-77-81. Croot, Ernie; Elsholtz, Christian (2004). "On variants of the larger sieve". Acta Mathematica Hungarica. 103 (3): 243–254. doi:10.1023/B:AMHU.0000028411.04500.e2.

Worked examples

Example 1 — a first encounter with Larger sieve

Start with the simplest possible case. Write down what Larger sieve claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Larger sieve before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Larger sieve ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Larger sieve

In research: Larger sieve appears in science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Larger sieve in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Larger sieve is common in secondary-school and first-year university syllabi. It links to neighbouring topics Sieve theory, so understanding it makes those chapters shorter.
In everyday life: Look for Larger sieve outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

Affiliate

Preply — study more efficiently by working with a personal tutor. 50% off.

How to study Larger sieve in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Larger sieve means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Larger sieve out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Larger sieve in simple terms?

In number theory, the larger sieve is a sieve invented by Patrick X. Gallagher.

Why does Larger sieve matter?

Because it connects several science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Larger sieve?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Larger sieve.