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]).$
###Variation
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.
Motivations:
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.)
Examples:
-
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.)
-
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$.
-
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.
-
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..$.
Best Answer
Let me first comment on your examples:
The record is acually $t=n^{0.525}$, due to Baker, Harman and Pintz.
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.
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).
http://arxiv.org/abs/1207.0842
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.