# Generalization of Bertrand's Postulate

Bertrand's postulate states that there is a prime $p$ between $n$ and $2n-2$ for $n>3$. According to Dirichlet's theorem we have that a sequaence $$a\cdot n+b$$ has infinite primes iff $a$ and $b$ are relatively prime. So in some sense, Bertrand's postulate gives a maximum of time for encountering a prime in the sequence $$2\cdot n+1$$ So, the question is: there is a generalization of Bertrand's Postulate for sequences $a\cdot n+b$ that accomplish the Dirichlet's theorem?

EDIT: (For a more concise explanation of the particular generalization.) We know that given $$a_n=2\cdot n+1$$ we have that for all $m$ there is a prime in the sequence greater than $a_m$ and less than $a_{2m}$. So, the thing is that if there is some generalization of Bertrand's Postulate using the sequence form, for an arbitrary sequence $$c_n=a\cdot n+b$$ with $a$ and $b$ coprime. Something as, for every relatively prime $a$ and $b$, there is a $k\leq a\cdot b$, such that for all $m$ there is a prime in the sequence between $c_m$ and $c_{k\cdot m}$.

Such kind of thing is what I am looking for.

• I believe you want e.g. "There always exists a prime in the arithmetic progression $a\pmod{q}$ between $n$ and $f_{a,q}(n)$ for $n\ge k_{a,q}$." There's Linnik's theorem to bound the first prime from above. Cramér's model should suggest the number of primes in the progression less than or equal to $x$ is $$\frac{\pi(x)}{\phi(q)}+O((x/q)^{1/2}\log(qx))$$ but Maier's theorem throws a wrench at this; see here. – anon Sep 6 '11 at 21:42
• Your type of generalization will also be interesting -although I would be more comfortable if $f_{a,q}$ and $k_{a,q}$ would be concrete easily computable things, but for that normally is requiered first the othe. I will look the material you cite, because it seems interesting and due that I am only some kind of beginner in number theory. – Josué Tonelli-Cueto Sep 7 '11 at 8:24
• The facts I cited are only related commentary on the distribution of primes in arithmetic progressions. It seemed to me the statement about primes being between $n$ and $f(n)$ would be a natural generalization, but such an $f$ might not be linear as it is in the basic $1\pmod2$ case. – anon Sep 7 '11 at 8:41

One generalization of Bertrand's postulate I know is a theorem of Sylvester and Schur. See for example http://www.math.uiuc.edu/~pppollac/sschur.pdf

The theorem says that for any positive integer $k$ the product of $k$ consecutive integers greater than $k$ contains a prime factor greater than $k$.

I hope this helps you somehow.

• Thanks, although I am interested in generalizations for sequences of Dirichet's theorem more beacuse I want to know if one can guarantee computationally if there is a maximum time to find a prime in the next prime from a given term. Nevertheles, it is an interesting generalization. – Josué Tonelli-Cueto Sep 6 '11 at 21:04

The answer is that there is such a generalization of Bertrand Postulate. For fizing constants, in the rest of the answer $a$ and $b$ will be coprime numbers, and $c_n$ will be given the sequence by

$$c_n=a+bn$$

We consider the prime number theorem for arithmetic progressions, this say that

$$\pi_{a,b}(x)\sim \frac{1}{\varphi(b)}\frac{x}{\log x}\text{,}$$

where

$$\pi_{a,b}(x)=\text{Card}\{p\leq x\,|\,p\text{ is prime and }p\equiv a\text{ (mod }b\text{)}\}\text{,}$$

$\phi$ is the Euler's totient function and $\sim$ denote that the limit of the quotient of the two functions tends to $1$ as $x$ tends to infinity. Let now $\rho_{a,b}$ be given by

$$\rho_{a,b}(n)=\text{Card}\{k\leq n\,|c_n\text{ is prime}\}\text{,}$$

we can show by straighforward calculation that

$$\rho_{a,b}(n)=\pi_{a,b}(a+bn)-\pi_{a,b}(a)\text{.}$$

From this, we have by the previous theorem that

$$\rho_{a,b}(n)\sim \frac{1}{\varphi(b)}\frac{a+bn}{\log (a+bn)}\text{,}$$

and so, by standard methods of analysis,

$$\rho_{a,b}(n)\sim \frac{b}{\varphi(b)}\frac{n}{\log n}\text{.}$$

Here, we can show, that for all $\varepsilon>0$,

$$\lim_{n\to \infty}\rho_{a,b}((1+\varepsilon)n)-\rho_{a,b}(n)=\infty$$

and thus define $N_\varepsilon$ as the first $n$ for which the previous difference is positive for all natural numbers greater or equal than it, i.e. $\rho_{a,b}((1+\varepsilon)n)-\rho_{a,b}(n)$ is positive for all $n\geq N_\varepsilon$ and negative for $n=N_\varepsilon-1$.

Therefore, we conclude that given $\varepsilon>0$, for all $n\geq N_\varepsilon$ there is a $k$ between $n$ and $(1+\varepsilon)n$ such that $c_k$ is prime. Furthermore, we can make $\varepsilon$ big enough such that $N_\epsilon$ is zero, since

$$\varepsilon\mapsto N_\varepsilon$$

is monotonous decreasing function. In this way, we obtain Bertrand's postulate for arithmetic progressions.

Here is another generalization

Let $$n$$ and $$k$$ be positive integers such that $$n > 1.1\log(2.5k)$$ then there are at least $$k-1$$ primes between $$n$$ and $$kn$$.