MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

In Harman's book "Prime Detecting Sieves" he describes a method to prove that a set contains primes if we have enough Type I and Type II information for it. As shown by Selberg's example of the set of numbers with an even number of prime factors Type I information is not sufficient to detect primes. Harman's methods require the Type II information to be given on sufficiently long intervals so that the sums we cannot give assymptotic formulae for are sufficiently small. Is it possible to prove, by giving a suitable counterexample, that if we have Type I information but only a very small amount of Type II information then we can't detect primes?

Let $A$ be the set in which we are interested, and suppose that $A\subseteq B$, the set of integers in $[x/2,x)$. Then, for a suitably small error $E$ and arbitrary bounded coefficients $a_m,b_n$ a Type I estimate is of the form $\sum_{mn\in A,m\leq M}a_m=\lambda \sum_{mn\in B,m\leq M}a_m+O(E)$ and a Type II sum is of the form $\sum_{mn\in A,x^\alpha\leq m\leq x^{\lpha+\beta}}a_mb_n=\lambda \sum_{mn\in B,x^\alpha\leq m\leq x^{\lpha+\beta}}a_mb_n+O(e).$ I am then wondering whether there are examples of sets satisfying these conditions for some $M,\alpha$ and sufficiently small $\beta$ which contain no primes. For definiteness take $M=x^{3/4}$ and $\alpha=1/4$.

share|cite|improve this question
Can you define "Type I" and "Type II"? – Qiaochu Yuan Jun 22 '12 at 13:48

I think (assuming that B is fairly dense) only an epsilon of Type II information is needed to detect primes, but then one needs very good Type I information (with M allowed to become very close to x). For instance, if one takes Vaughan's identity

$$\sum_n \Lambda(n) f(n) = \sum_{a \leq U} \sum_b \mu(a) \log(b) f(ab) - \sum_{a \leq U} \sum_{b \leq V} \sum_c \mu(a) \Lambda(b) f(abc) $$ $$ + \sum_{a > U} \sum_{b > V} \sum_c \mu(a) \Lambda(b) f(abc)$$

for any $U,V$ and $f$ supported on the region $n > V$, then by selecting $U := x^{3/4-\beta}$, $V := x^{1/4}$ and $f(n) := (1_A(n) - \lambda 1_B(n)) 1_{n > V}$, Vaughan's identity expresses $\sum_n \Lambda(n) f(n)$ in terms of Type I sums up to level $x^{1-\beta}$ and Type II sums in the regime you suggested. The idea to make the Type I sums do almost all the work is quite useful, for instance in Bombieri's asymptotic sieve. (I also used it recently to establish that every odd number is expressible as the sum of at most five primes.) Of course this only works when one has extremely good equidistribution information on A, which either requires A to be very "smooth" or to assume some powerful equidistribution hypothesis, such as the Elliot-Halberstam conjecture. There's no free lunch in this business!

But I doubt that one can get by if one only has an epsilon of Type II information and if the Type I information is limited to some level well below x, such as $x^{3/4}$; somehow one is not covering enough cases to control any reasonable divisor sum expansion (whether of Vaughan type or otherwise). But I don't have an explicit counterexample at hand, but it should be something like a set A which is biased with respect to a weight function such as $w(n) := \sum_{a \sim x^{0.8}; b \sim x^{0.1}; ab|n} \mu(a) \Lambda(b)$ (which vanishes at primes, and so allows for A to have an anomalous prime count) but which obeys all the Type I and Type II axioms one is assuming (note that one should need Type I information at level $x^{0.9}$, or Type II information with $[\alpha,\alpha+\beta]$ containing 0.1, 0.2, 0.8, or 0.9, in order to detect the correlation with w).

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.