Half-dimensional interval sieve Created 2026-10-06 Updated 2026-10-14
Sieve an interval of length by the prime two and the primes congruent to three modulo four, with local densities . Take and . The truncated Euler-product lower bound, the Mertens first theorem and the reciprocal-prime sum in residue class one modulo four give . The interval counts have bounded remainders, whose sum is by the summatory bound for three to the prime omega. Hence the number surviving is , uniformly in the location of the interval.
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 27 3 b Solution 2026-10-06
Write , where is the prime omega function. If , its contribution to the Dirichlet convolution isSince , summing over the prime factors proves the log-weighted convolution bound for three to the prime omega, . On , , henceThis is the required inequality. The standard Chebyshev estimate bounds its right side by . To bound the latter sum, use multiplicativity and extend to all numbers with prime factors at most :The Mertens second theorem states . Taking logarithms of the product, with a summable remainder, gives . Therefore the product is , proving the summatory bound for three to the prime omega in the required range:
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 27 5 a Solution Created 2026-10-03 Updated 2026-10-06
In the level- convention used here, the Selberg upper-bound sieve states that a nonnegative sequence with sieve distribution satisfiesIt follows by minimizing the quadratic form with the Selberg sieve weights and using the Selberg least-common-multiple weights bound .
Sieve the interval by two and by the primes congruent to three modulo four, up to . The interval divisor counts giveThus , , and uniformly in the location of the interval. Take and .
To bound , let and form the Euler product over the forbidden primes at most . The given reciprocal-prime sum in residue class one modulo four, subtracted from the Mertens second theorem, yieldsMoreover, the Mertens first theorem bounds the logarithmic mean by for large . The truncated Euler-product lower bound gives .
The full-range summatory bound for three to the prime omega bounds the error by , which is . Every integer whose prime factors are all congruent to one modulo four survives this finite sieve. Therefore the half-dimensional interval sieve givesThe constants are independent of . Enlarging them covers the bounded range of before the asymptotic product estimates apply, so the result holds throughout .