11
$\begingroup$

My question concerns the following sieve (call it S), which was an exercise in applying some elementary aspects of Brun's sieve while reading Halberstam's text.

Using the Chinese Remainder theorem we can show:

(S) The number of $n$ such that $n,n+2$ are co-prime to $p_k\#$ for $n =1,2,...,p_k\#$ is $$\prod_{i=1}^k (p_i-2).$$

So for example on $[1,5\#]$ there are 3 pairs n,n+2 co-prime to 2,3,5 and those are $(11,13),(17,19),(29,31).$ The smallest prime dividing any sieved $n$ is 7, and because $7^2$ is larger than $2\cdot3\cdot5$ it must be that the largest power of this minimal prime (a factor of $n$ or $n+2$) is 1. Therefore the sieved pairs are twin primes.

For larger $p_k\#$ the minimal prime $p$ (the smallest such that $p< p_{k}\#< p^2$) is larger than $p_{k+1}.$ Put another way, the power $\Omega$ of $p_{k+1}$ such that $(p_{k+1})^{\Omega}\leq p_k\#$ is increasing. The best we can say using (S) is that $n,n+2$ have at most $\Omega$ prime factors, and $\Omega$ grows without bound as $k$ gets large.

For small $k$ we can avoid the problem in a facile way. Call the modified sieve S'.

As an example, on the interval $[1,13\#]$ the number of $n,n+2$ co-prime to $13\#$ is 1485. Unfortunately $p_{k+1}=17$ and $17^3 <13\#. $ So the best we can say is that $n,n+2$ have at most 3 prime factors. However if we sieve (the same interval) using $p_{40}\#=173\#,$ then $p_{k+1} = 179$ and 179, not by accident, is the smallest prime $p$ such that $p < 13\# < p^2.$

Because we are using more primes to sieve the same interval, the number of counted (co-prime to $p_{40}\#$) pairs $n,n+2$ falls from 1485 to 456. On the other hand, because 179 is the smallest prime occurring in any sieved pair and cannot occur as a power greater than one (else it exceeds 13#), all 456 pairs are twin primes (I checked.)

While one might hope show that the cardinality of prime pairs $n, n+2$ is increasing with $k$ despite the need to choose increasingly large minimal primes (in the sense above), what seems more likely (because simple approaches like this were discarded en route to Brun's sieve) is that as increasingly large primes are needed, even if they are small compared to $p_k\#$, a point is reached beyond which $|\{n, n+2\}|$ is no longer increasing. But the reason for this eludes me.

There may be some other issue here, so my question is:

Can someone explain why S' fails, or give an argument that the number of sieved pairs using S' above will eventually fail to increase as $k$ gets large?


In the spirit of "What have you tried?" let $p_{k+m}$ be the the smallest prime s.t.

$p_{k+m}< p_k\# <p_{k+m}^2 $ or

$$p_{k+m}~ \text{minimal s.t.}~ p_{k+m} > p_k\#^{(1/2)}.$$

For large $k,$ $p_{k+m}$ is relatively close to $p_k\#^{(1/2)}$ and the proportion of the interval $[1,p_k\#]$ being sieved is

$$\sim(1-1/\sqrt{p_k\#}).$$ So the number of primes greater than $p_k$ on the interval $[\sqrt{p_k\#},p_k\#]$ is

$$\sim p_k\#/\log p_k\#\sim p_k\#/p_k.$$

The number of multiples of $p_{k+1}, p_{k+2},..., p_{k+m}$ on the same interval is

$$p_k\#/p_{k+1}+p_{k\#}/p_{k+2},... = p_k\#(1/p_{k+1}+1/p_{k+2}+...+1/p_{k+m})$$ and

$$1/p_k < 1/p_{k+1}+1/p_{k+2}+...+1/p_{k+m}. $$

So even though the number of primes is increasing, relatively few survive the sieve and we can't be sure the cardinality of sifted pairs is strictly increasing...?

Notation: $p\#$ := $2 \cdot 3 \cdot 5...\cdot p.$ The intervals $[1,p_k\#]$ are actually $[1,p_k\#+2]$ but it's hard to read and doesn't affect the question.

$\endgroup$
  • $\begingroup$ Won't edit this again but maybe the sieve works fine and it n just cannot be proven to increase as as $p_k$ increases w/o bound. Would still be interested in an answer that discusses the difficulties involved. $\endgroup$ – daniel Feb 24 '16 at 17:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.