Concept

Sieve — where it appears

A method of counting or finding numbers by removing, in turn, those divisible by each prime in a list. Counting what survives is inclusion–exclusion, and stopping that count early is what lets sieves bound quantities the exact formula cannot reach.

Named by 2 essays across 2 fields — each of them below, with the objects they name alongside it.

Two sums of reciprocals: 2.89 and climbing against 1.71 and level. Two curves against the logarithm of the bound: the sum of reciprocals of all primes, rising steadily, and the sum over the twin primes, flattening towards a limit.

The sieve that cannot finish

Sifting out the composites is the oldest method in the subject and it has a ceiling nobody has raised. The reciprocals of the twin primes add to a finite number, so no argument that measures thickness can reach them — and the inclusion–exclusion every sieve truncates goes wildly wrong before it goes right.

number · Infinitude of primes

A 6-sided die rolled 6 to 40 times: some face missing, and the sum stopped early. Curves of the chance that some face of a die has not yet appeared against the number of rolls, with the inclusion–exclusion sum stopped after one, two and three terms drawn around the exact curve.

A sum stopped early still says something

Inclusion–exclusion corrects an overcount, then the correction's overcount, and so on to the end. Stop after any number of terms and the result is not merely an approximation: after an odd number it is too high and after an even number too low, always. So two or three terms bracket an answer whose full sum is out of reach — as long as the events being counted are rare.

probability · Inclusion exclusion

Named alongside it

The objects these essays reach for when they reach for this one.

Alternating series Approximation Complementary counting Convergence Counting argument Derangement Inclusion exclusion Open problem Prime Twin primes Union bound

All concepts