10
$\begingroup$

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.

  • 0
    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.2011-09-07

3 Answers 3

1

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.

3

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.

  • 0
    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.2011-09-06