Problem 1: Find a (not extremely artificial) set A of integers so that for every $n$, $|A\cap [n]| \le n^{0.499}$, ($[n]=\{1,2,...,n\}$,) where you can prove that $A$ contains infinitely many primes.

Problem 2: Find a (not extremely artificial) set $A$ of integers so that for every $n$, $ |A\cap [n]| \le n^{0.499}$, where you can prove that

$ \sum \{\mu(k): k \le n, k \in A\} = o(|A \cap [n]).$


For problem 1 it makes sense to ask not just about infinitely many primes but about a result regarding the density of primes which is of the full strength of the prime number theorem. (In fact, I thought about Problem 2 as a weak form of problem 1 but this is not the case the way I formulated it.)

Problem 3: Find a (not extremely artificial) set $A$ of integers so that for every $n$, $|A\cap [n]| \le n^{0.499}$, ($[n]=\{1,2,...,n\}$,) where you can prove that the density of primes in $A$ in the interval $[n]$ is $1/\log n+o(1)$.

Perhaps the best way to formulate and think about Problem 3 is in terms of orthogonality with the Van Mangold function.


This question is motivated by various recent results on Mobius randomness and infinitude of primes in various exotic sets, and also on this question: Why so difficult to prove infinitely many restricted primes?.

(The set of $p_{n^5}$ is extremely artificial and I suppose that a set that can be ordered in a sequence (not necessarily increasing) such that $a_n$ can be provably computed in $poly (\log |a_n|)$ steps is not extremely artificial.)


  1. A very natural example is an interval of the form $[n,n+t]$ and here indeed the best known absolute results is when $t=n^{0.535..}$. RH allows $t=\sqrt n \log n$ and it looks that here the $n^{1/2}$ is a viable barrier. (Here I base the info on the paper: A Survey of Results on Primes in Short Intervals by Cem Yalçın YILDIRIM.)

  2. There is a result by Friedlander and Iwaniec that there are infinitely many primes of the form $a^2+b^4$. Here the density is above the square-root barrier, but I don't know if there are any insights regarding improvement to, say, $a^3+b^7$.

  3. There is a result by Elkies about the infinitude of supersingular primes. Those primes are conjectured to be of density $n^{1/2}$ among the first $n$ numbers but provably it is only known that they are of density less or equal $n^{3/4}$ I don't know if there are Elkies-like results that can lead (provably or conjecturally) to sparser sets of primes.

  4. There is a "PNT for majority functions" result of Bourgain that implies that there are infinitely many m-digits primes with more than a fraction $c$ of their binary digits are ones, for some $c=1/2+m^{-\rho}$, for some $\rho<1$ Having this for $c=0.9$ will cross the square root barrier. (Update based on Christian's answer: )Eric Naslund used the results about primes in intervals to prove it for $c=0.737..$.

  • $\begingroup$ Can't you use Tao and Ziegler's result to produce sets with this property? $\endgroup$
    – user36648
    Jul 6, 2013 at 21:53
  • 1
    $\begingroup$ Could you please be more specific. When I hear Tao--Ziegler my first association is polynomial progressions in the primes. But it is not apparent to me that this has to say something about this problem. But possibly it does or you mean a different results. $\endgroup$
    – user9072
    Jul 6, 2013 at 22:03
  • $\begingroup$ If you define 'not extremely artificial' to be 'the n-th term is constructable by a poly-log time algorithm (in the bit length of n)' then this is essentially equivalent to getting around the square root barrier in the prior Polymath "deterministic methods to find primes" problem, which asks for an algorithm that constructs a $\log(n)$ bit prime in time $n^{1/2-\delta}$. See arxiv.org/abs/1009.3956. Notice that many natural candidates for 'not extremely artificial' are efficiently constructable in this sense. $\endgroup$
    – Mark Lewko
    Jul 7, 2013 at 0:20
  • 1
    $\begingroup$ @Gil, perhaps I'm misunderstanding something. If one wanted a prime near N, then one could just produce (via the algorithm) and test each of the $\ll N^{.49}$ values of the polynomial less than N for primality with AKS (which would run in $O( N^{.49+\epsilon})$ time. Now there is a slight issue that if all one knows is that the set contains primes infinitely often this may fail for some bit lengths. (cont.) $\endgroup$
    – Mark Lewko
    Jul 7, 2013 at 6:21
  • 1
    $\begingroup$ Dear Mark, this looks correct, at least for the sequence I mentioned or similar examples. In general you may need to go over all N numbers to tell which of them belongs to A so it is not clear why in general a positive answer to Problem 1 gives an $N^{1/2-\delta}$ algorithm for finding a prime with log N digits. Also it is not clear why from such an algorithm you get a positive answer to Problem 1. $\endgroup$
    – Gil Kalai
    Jul 7, 2013 at 7:41

1 Answer 1


Let me first comment on your examples:

  1. The record is acually $t=n^{0.525}$, due to Baker, Harman and Pintz.

  2. A slightly thinner sequence of this type is $n=a^3+2b^3$, investigated by Heath-Brown, and also cubic polynomials in two variables, by Heath-Brown and Moroz, eprints.maths.ox.ac.uk/00000163/01/morozcub2.pdf

Other polynomials in two or more variables, like those that you suggest, are certainly not known by today's methods.

  1. Here is a sketch to obtain primes with a density of 0.7375 one bits (compare also this paper by Eric Naslund https://arxiv.org/abs/1211.2455

and his answer on mathoverflow, to a question by Gil Kalai Primes with more ones than zeroes in their Binary expansion their-binary-expansion/97345#97345

By Baker-Harman-Pintz one can fix the first 0.475n bits as one. With $x=2^n$ There are $\gg x/\log x$ many primes in the interval [2^n-(2^n)^0.525, 2^n]. For the remaining 0.525n bits about 50% must be 0 and 50% ones. If the proportion of one bits was smaller, then estimating the tail (sum of binomial coefficients) would show the number of primes is too small.

So altogether the asymptotic density of one bits can be as large as $(0.475+1/2\, 0.525)n=0.7375n$.

Here is a paper, where a similar method was used to find quadratic non-squares or even primitive roots, with only few one-bits (less bits than the least non-square or least primitive root might need).


Now an example for a sequence with quite small counting function (Problem 1).

Let us first look at large and sparse, but finite sets. Let $F_n=2^{2^n}+1$ be the $n$-th Fermat number.

Let $D(F_n)$ be the set of its divisors. Observe that the number of divisors is (by Wigert's bound) $d(F_n)=O(exp (c \frac{\log F_n}{\log \log F_n})=O(\exp(c' 2^n/n)$.

Let $S(k)=\cup_{n=1}^k D(F_n)\subset [1,2^{2^k}+1]$. Observe that $|S(k)|= O(k \exp(c' 2^k /k)< (F_k)^{0.499}$.

The set of divisors of the Fermat numbers contains also the prime factors (for each $F_n$ at least one new prime number, as the Fermat numbers are coprime).

Well, to extend this to an infinite set we need to take care of the fact that with $F_{n+1}$ one possibly also adds smaller elements, so that the counting becomes a bit more tricky. But these added elements are not very small, as one can show that the prime factors of $F_n$ are at least of size $2^n$. So maybe one can take the union over a thin subset of the Fermat numbers, such as $\cup_{n=1}^k D(F_{2^n})$ or similar,

Or one only takes the second smallest element $s_n$ of $D(F_n)$, (which must be a prime!).

$S= \cup_{n=1}^{\infty} s_n$.

Note again, that the $s_n$ are distinct and are (at least) exponentially increasing, $s_n>2^n$, by properties of the Fermat numbers.

In case anybody thinks this is an artificial sequence, equivalent to writing down some prime numbers: well, the prime divisors of sequences such as $s_n=n^2+1$ or $s_n=\lfloor 2^n/n\rfloor$ might not work, as these might be too dense.

  • 1
    $\begingroup$ There is a fundamental difference with FI and HB. The first establishes bilinear bounds via a Cauchy step, the main tool being the lacunarity of the squares. The operative range is $\sum_m|\sum_n \gamma(n)a_{mn}|$ where $\gamma$ is a lot like $\mu$ (sum of $\mu$ up to some parameter), and $n\sim N\gg x^{1/4}$ so the sum has mass, but also $N\ll x^{1/2}/\log^B$ so $m\sim M\gg x^{1/2}\log^B$ so upon Cauchy + order-swap the $m$-sum is feasible lattice point counting. So 3/4 is a natural limit. Meanwhile, HB has a multi-dimensional large sieve, on a comparison basis, so this limit is not there. $\endgroup$
    – v08ltu
    Jul 8, 2013 at 2:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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