12
$\begingroup$

We have some theorems about the density of prime numbers, the most famous one is probably the prime number theorem.

My question is

about the density of primes when we choose random numbers from a different distributions. The main example I have is numbers of the form $2^a3^b5^c+1$. Are there theorems similar to the prime number theorem when we restrict the numbers to those of this form?

More generally, let's call a set $A \subseteq \mathbb{N}$ efficiently enumerable if there is a (deterministic) polytime algorithm enumerator for $A$, i.e. a polytime algorithm that whose range is exactly $A$ (and for simplicity lets assume that the enumeration is also injective so every member of $A$ appears exactly once) (is there a common name for this in the literature?).

Are there efficiently enumerable sets such that a theorem similar to the prime number theorem or something stronger holds for the distribution of primes in them?

Note that if we can find prime numbers in deterministic polynomial time, then the density would be one for the corresponding set, but that is open for now, so can we get closer to density 1 by replacing $\mathbb{N}$ with another efficiently enumerable set?

This came out of a discussion a few days ago about better ways of finding primes in practice. If there is a deterministic polytime algorithm to find primes then the question for the corresponding enumeration would be trivial, but since that is open, one may want to see if there are other efficiently enumerable sets that can be used to find primes in practice. This might be related to the number of random bits that is used by a probabilistic polytime algorithm to generate primes also.

What are the known upperbounds for the number of random bits (used by a probabilistic poly-time algorithm) are known for generating primes?

Improve this question
$\endgroup$
15
  • 1
    $\begingroup$ I am not sure what you can hope for in the second question about primes in an “efficiently enumerable” set. Although the definition of “efficiently enumerable” is unclear to me (you say the algorithm A is polynomial-time, but polynomial in what?), the set 2ℕ+4 should be efficiently enumerable, and it does not contain any primes. $\endgroup$
    – Tsuyoshi Ito
    Mar 10, 2011 at 12:14
  • 1
    $\begingroup$ Since primality is in P, isn't the algorithm that enumerates all primes efficient by your definition? Or do you want an algorithm that generates numbers of length $\ell$ in time polylog($\ell$)? You should be clearer in this part. $\endgroup$
    – Peter Shor
    Mar 10, 2011 at 15:29
  • $\begingroup$ Could you be more specific about what you mean by generating primes? Presumably you mean sampling the prime numbers in a certain range according to a certain distribution, but it would be helpful (to me at least) if you could give both the range you consider (as a function of $n$) and the probability distribution you need (does it have to be uniformly at random, or can the probability of generating a particular prime vary as a function of it's distance from other primes according to some metric?). $\endgroup$
    – Joe Fitzsimons
    Mar 10, 2011 at 15:45
  • $\begingroup$ @Tsuyoshi, @Peter: I assume what Kaveh meant is that there is a polynomial-time function $f$ (polynomial in the size of its input, as usual) such that it's range is exactly $A$, i.e. $f(\Sigma^*) = A$. This notion is related to, but not the same as, P-printability (see e.g. ftp.cs.rutgers.edu/pub/allender/pprint.pdf). $\endgroup$
    – Joshua Grochow
    Mar 10, 2011 at 17:23
  • 6
    $\begingroup$ @Kaveh: if you just require the primes in A to have the same density as the primes in N, then the quantitative version of Dirichlet's theorem says that all arithmetic progressions which aren't obviously composite have the correct density of primes. If you require that the set A have an asymptotically higher density of primes, i.e., $\omega(1/n)$ for numbers of length n, I suspect this is an interesting number theory question. $\endgroup$
    – Peter Shor
    Mar 11, 2011 at 20:13

0

Reset to default

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.