Home » 2011 » March (Page 2)

Monthly Archives: March 2011

Analogues of Cramer’s conjecture

March 7, 2011 10:46 am / 1 Comment on Analogues of Cramer’s conjecture

Abstract: In this post, I present my approach to Cramer’s conjecture on the gap between consecutive primes. However since the sequence of primes $p_n$ are just a special of the sequence of numbers asymptotically equidistributed modulo one $s_n$ , I have considered the general problem of estimating the gap between consecutive terms of $s_n$ . Applying this general theory on prime numbers show why Cramer’s conjecture should possibly be true.

1. Introduction

One of the most famous open problems in the theory of primes is the gap between consecutive primes. Given two consecutive prime numbers $p_{n+1}$ and $p_n$ , how large can the difference $g(n)=p_{n+1}-p_n$ be? The answer to this question has baffled mathematicians for almost a century; however continuous progress has been since 1920 when Harald Cramer’s proved on the assumption of the Riemann Hypothesis, that

$p_{n+1} - p_n = O(p_n^{0.5}\ln p_n)$ .

Cramer’s Conjecture: Cramer applied probabilistic methods to estimate an upper bound on $g(n)$ and in 1936, he suggested that

$\displaystyle{\limsup_{n \rightarrow \infty}\frac{p_{n+1} - p_n}{\ln ^2 p_n} = 1}.$

This statement is known as the Cramer’s conjecture. Intuitively, this means the gaps between consecutive primes are always small, and it quantifies asymptotically just how small they can be. This conjecture has neither been proved nor disproved. In Cramer’s model one assumes that the probability that a natural number $x$ is prime is $1/\ln x$ . This model was consistent with empirical and in 1966, Gallagher showed that the Hardy-Littlewood conjecture on $k$ -tuples was consistent with Cramer’s model.

Cramer-Granville’s Conjecture: Despite so much evidence in support of Cramer’s probabilistic model, in 1985, Helmut Maier proved a result that actually contradicts the predictions of Cramer’s. The problem with Cramer’s model is that it fails to take into account divisibility. Thus, for the primes $p > 2$ , the probability that $p+1$ is prime is not $1/\ln(p + 1)$ as suggested by the Cramer model but rather $0$ since $p+1$ is even. Further $p+2$ is always odd; therefore it is twice as likely to be prime as a random natural number. Thus $n$ and $n+2$ being primes are not independent events. Based on Maier’s result, in 1995, Andrew Granville refined Cramer’s model and conjectured that

$\displaystyle{\limsup_{n \rightarrow \infty}\frac{p_{n+1} - p_n}{\ln ^2 p_n} \ge 2e^{-\gamma}}$

where $\gamma$ is the Euler-Mascheroni constant. The modified statement

$p_{n+1} - p_n < M\ln ^2 p_n$

with $M>1$ is known as the Cramer-Granville’s Conjecture.

Firoozbakht’s conjecture: In 1982, Iranian mathematician Farideh Firoozbakht the following conjecture which is lesser known but appears to have far reaching consequences in the study of the gap between consecutive primes that the sequence $p_n^{1/n}$ decreases for all $n \ge 1$ . This conjecture has been computationally verified for all primes up to $10^{12}$ . From the prime number theorem, it can be shown that Firoozbakht’s conjecture implies

$p_{n+1} - p_n < \ln ^2 p_n - \ln p_n + 1$ .

This upper bound is not only stronger that the Cramer’s conjecture but it also contradicts Granville’s limit $2e^{-\gamma}$ . Thus either Cramer-Granville’s Conjecture is false or the Firoozbakht’s conjecture is false. But which one if false? We don’t know for sure. Currently the best unconditional result is far from either; $g(n)=O(p_n^{0.535})$ which was proved by R. Baker and G. Harman.

2. Sufficient conditions for Cramer’s conjecture

Lemma 1. Let $c_n$ be the largest real such that

$\displaystyle{p_n ^{\frac{1}{n}} > \Big(1-\frac{c_n \ln p_n}{n^2}\Big)p_{n+1} ^{\frac{1}{n+1}}}.$

If there exists a natural number $n_0$ such that for all $n>n_0$ ,

$c_n \le 0$ then Firoozbakht’s conjecture or,
$c_n$ is a positive constant then the Cramer-Granville conjecture is true.

This can easily be proved by finding the upper bound on $p_{n+1} - p_n$ from the inequality mentioned in the lemma.

Let $p(n) = p_n ^{1/n}$ . If $p(n) > p(n+1)$ , we define $a_n$ as

$\displaystyle{a_n = -\frac{1}{\ln n}\ln\Big(\frac{p(n)}{p(n+1)} - 1\Big)}.$

Lemma 2. If there exists a natural number $n_0$ such that for all $n>n_0, a_n \ge 0$ then Firoozbakht’s conjecture is true and this would imply that

$p_{n+1} - p_n < \ln^2 p_n - \ln p_n + 1$ .

This lemma is also proved by assuming the hypothesis in the statement of the lemma and finding the upper bound on $p_{n+1} - p_n$ . Thus we see that we can gain new insights in to the difference between consecutive primes by studying the quantity $p(n) = p_n ^{1/n}$ and more specifically, we need a good estimation of the ratio $p(n)/p(n+1)$ .

3. Gap between consecutive terms of sequences asymptotically equidistributed mod 1

The following idea is drawn form Firoozbakht’s conjecture. Let $s_n$ be asymptotically equidistributed modulo one and let $h(n)=s_n^{1/n}$ . If we can find a lower bound on $h(n)/h(n+1)$ than by algebraic manipulations, we can obtain an upper bound on the gap $s_{n+1} - s_n$ . The first task is to find a good estimate of $h(n)=s_n^{1/n}$ . Since $s_n$ is asymptotically equidistributed mod 1, we have

$\displaystyle{\lim_{n \rightarrow \infty}\frac{1}{n}\sum_{r \le n}f\Big(\frac{s_r}{s_n}\Big) = \int_{0}^{1}f(x)dx}.$

Taking $f(x) =x^{1/n}$ , and simplifying we have:

Lemma 3. If $s_n$ is asymptotically equidistributed mod $1$ and $\lim_{n \rightarrow \infty}s_n^{1/n} = 1$ , then

$\displaystyle{s_n^{1/n} = \frac{n+1}{n^2}\sum_{r \le n}s_r^{\frac{1}{n}} + o(1)}.$

Let $j(n) = \frac{n+1}{n^2}\sum_{r \le n}s_r^{\frac{1}{n}}$ and let $\epsilon _n = o(1)$ be the error term so that $h(n) = j(n) + \epsilon _n$ .

Lemma 4. Assuming the hypothesis of Lemma 3, there exists a positive intger $n_0$ and a positive constant $c$ such that for all $n > n_0$ ,

$\displaystyle{\frac{j(n)}{j(n+1)} > 1 - \frac{c\ln s_n}{n^2}}.$

Although $h(n) = j(n) + o(1)$ , Lemma 4 does not directly imply that

$\displaystyle {\frac{h(n)}{h(n+1)} > 1 - \frac{c\ln s_n}{n^2}}.$

should hold for all sufficiently large $n$ . However if this relation were true than we would have been able to show that

$\displaystyle{s_{n+1}-s_n < \frac{(2+\epsilon) s_n \ln s_n}{n} + 1}.$

To be continued.

References

[1] http://arxiv.org/abs/1010.1399

Benford process tends to minimize product

March 6, 2011 1:29 pm / Leave a comment

Consider the simple question, what is the largest product of two numbers that can be formed using all the ten digits of the decimal system, each digit used exactly once. We have two answers $\{96420, 87531\}$ and $\{9642, 875310\}$ . Continuing on the same line, we can seek three numbers that give the maximum product and so on. In general we can ask: Given a set $A$ of $n$ single digits numbers, not necessarily distinct, form a set of $k$ numbers using all the given numbers i.e. of the digit 2 occurs thrice in the set $A$ then we can use the digit 2 exactly three times while forming our set with the maximum product. Trivially we can see that there can be one of more answer depending on weather the number $0$ is a element of $A$ because we can form more and one set with same product by placing the $0$ in the unit’s place of any number that does not end in a $0$ .

Suppose that a certain random process can generate one set of $k$ number per run using all the elements of a given a set of numbers $A$ . Hence an exhaustive run of this process will generate all possible set of numbers with $k$ elements. Let the set of all numbers generated by this random process satisfy the conditions of Benford Law. We shall call such a process as a Benford process and formally define it as:

Benford Process: A Benford process is a random process which generates numbers that satisfy the conditions of Benford Law.

Now if we run a Benford process once, how likely is that the process generates a set of numbers that give the maximum product. In this article we shall see that under the conditions of Benford Law, the probability that the $k$ numbers so generated will have the largest product should be the least. In other words, numbers generated a random process which satisfies the conditions of Benford Law are least likely give the maximum product.

Theorem 1. For any give $k$ and a set of single digits numbers $A$ , not necessarily distinct, the numbers generated by a Benford process, using all the elements of $A$ , is least likely to have the maximum product.

Proof: The proof of this theorem follows trivially form the following lemma.

Lemma 1. Let $A=\{d_1, d_2, ... , d_n\}$ be a set of $n$ digits in base 10 notation, not necessarily distinct, such that $0\le d_i \le d_{i+1}\le 9$ . If a set $M_k (A)$ of $k$ elements is formed using only and all the elements of the set $A$ then the elements of $M_k (A)$ are given by

$a_j = d_{n-k+j}d_{n-2k+j}...d_{n-rk+j}$

where $n-rk+j \ge 1, j=1, 2, ... , k$ .

Thus larger a digit, the more significant position it occupies. According to the General Benford Law, the probability of a number starting with a larger digit in the most significant place is lower than that of number starting with a smaller number in the most significant place. Hence the theorem follows.

Mathematics: The Language of the universe

Monthly Archives: March 2011

Analogues of Cramer’s conjecture

Benford process tends to minimize product

Post navigation