13
$\begingroup$

This question on random versions of deterministic problems reminded me that many conditional results in number theory hold if the primes are in some sense random, and it is common knowledge that the Riemann hypothesis is tied up in this line of thought.

Now, off the top of my head it's not clear what "randomly distributed" really means in the context of the primes. I know that the RH would imply better versions of the prime number theorem, but that's not quite the same. So I am interested in a clarification of this as well as the following

Main question: what results would imply that, and what results would we gain from, the assumption that the primes are "randomly distributed"?

Improve this question
$\endgroup$
3
  • $\begingroup$ Many conjectures in Analytic Number Theory follow or are based on suitable 'random distribution assumptions,' for a certain type of Analytic Number Theory most likely even most; I am worried this will be a long list. If I may make a suggestion: asking for a high-level explanation illustrated by selected examples, might make a better question. $\endgroup$
    – user9072
    Commented May 20, 2011 at 20:36
  • $\begingroup$ I haven't investigated this to form an answer, but I do believe the Goldbach conjecture would follow if the primes were 'random'. $\endgroup$
    – Stanley Yao Xiao
    Commented May 20, 2011 at 21:24
  • $\begingroup$ In "practical" terms, this is presumably tied up with the question: is integer factorization hard? I.e., the security of RSA. $\endgroup$
    – Kimball
    Commented May 20, 2011 at 23:17

4 Answers 4

Reset to default
9
$\begingroup$

Since the primes aren't really random, it's not possible to state precisely the consequences of assuming that the primes are random in the same way that we can state precisely the consequences of the Riemann hypothesis or the axiom of choice. However, using the Cramér random model for the primes, one can "deduce" many conjectures about the primes, such as the Hardy-Littlewood prime tuples conjecture. There is a nice expository article by Chris Caldwell that explains how to use Cramér's model to deduce all kinds of number-theoretical statements.

Improve this answer
$\endgroup$
7
$\begingroup$

This is an excellent expository paper by Soundararajan bearing on your question.

Improve this answer
$\endgroup$
6
$\begingroup$

The Moebius function $\mu(n)$ is defined for squarefree integers $n$ as $(-1)^k$ if $k$ is the number of prime factors of $n$ (and $\mu(n)$ is defined as $0$ if $n$ is not squarefree). The Riemann hypothesis is equivalent to the statement $\forall \epsilon > 0, \sum_{n < x} \mu(n) = o(x^{1/2 + \epsilon})$. If, on the other hand, you choose $\nu(n) = \pm 1$ randomly for squarefree $n$ and zero otherwise, then by the law of the iterated logarithm, with probability one $\sum_{n < x} \nu(n) = O(\sqrt {x \log \log x})$.

Other randomness issues connected with the Riemann hypothesis for L-functions are estimates for sums of the type $\sum e^{2\pi i \alpha n}$ or $\sum \chi(n)$ for a Dirichlet character $\chi$, where $n$ may vary over the integers in an interval or just over primes in an interval (and I should have written $p$ in that case). The mean of these sums is usually easy to figure out and sharp estimates for the deviation from the mean are consequences of (or sometimes equivalent to) the Riemann hypothesis. You can phrase some of these things in terms of primes in arithmetic progressions but then it's not so easy to see the connection with randomness.

Improve this answer
$\endgroup$
6
  • 3
    $\begingroup$ I think you need a bound of $O_{\epsilon}(x^{1/2 + \epsilon})$ to be equivalent to RH. (In the probabilistic model, the law of the iterated logarithm suggests the partial sums will be greater than $O((x\ln \ln(x) )^{1/2})$ infinitely often.) $\endgroup$
    – Mark Lewko
    Commented May 20, 2011 at 21:25
  • $\begingroup$ @Mark: You are probably right, thanks. $\endgroup$
    – Felipe Voloch
    Commented May 20, 2011 at 21:35
  • 2
    $\begingroup$ What's interesting here is that the best conjecture so far on the size of $\sum_{n < x}{\mu(n)}$ is by Ng, which is that these sums are only greater than $C \sqrt{x} (\log \log \log x)^{5/4}$ infinitely often, but not any function that grows faster. So there's a bit of a disparity between the probabilistic model and the real thing. $\endgroup$
    – Peter Humphries
    Commented May 21, 2011 at 4:32
  • $\begingroup$ Since it's community wiki, I corrected the statements. $\endgroup$
    – Douglas Zare
    Commented May 21, 2011 at 4:45
  • 1
    $\begingroup$ @Qiaochu: What I mean is that the heurestic given by Ng (see near the end of cs.uleth.ca/~nathanng/RESEARCH/mobius2b.pdf) is justified by theoretical evidence in line with other, more accepted conjectures (Riemann hypothesis, linear independence hypothesis, and discrete moments of L-functions), in comparison to other conjectured growth rates of $\sum_{n < x}{\mu(n)}$, which, as Ng discusses, can vary greatly. $\endgroup$
    – Peter Humphries
    Commented May 22, 2011 at 3:21
2
$\begingroup$

Billingsley wrote a nice article on the relationship between numbers, random walks and Brownian motion.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .