Sunday, September 23, 2012

Tackling Andrica's conjecture

Andrica's conjecture is one of those mathematical statements which are extremely easy to formulate, but complicated to prove. In fact it hasn't been proved yet, to be more precise. Here we go, for all consecutive prime numbers $p_{n}$ and $p_{n+1}$, it happens that: $$\sqrt{p_{n+1}} - \sqrt{p_{n}}< 1$$

1. The first attempt

Let's start with an analogy, here is an inequality $p_{n+1} < 2\cdot p_{n}$ which is a direct result from Bertrand's postulate, proved by Chebyshev. As a result of this inequality, we have: $$0 < ln(p_{n+1}) - ln(p_{n}) < ln(2) < 1$$ But what is the relationship between natural logarithm and square root functions?

Well, let's have a look at the following function: $f_{1}(x)=\sqrt{x} - ln(x)$. First derivative of this function is ${f_{1}}'(x) = \frac{1}{2\cdot \sqrt{x}} - \frac{1}{x}=\frac{1}{x}\cdot \left ( \frac{\sqrt{x}}{2} -1\right )\geq 0$, for $\forall x\geq 4$. This means that $f_{1}(x)$ is ascending for $\forall x\geq 4$. As a result, for $\forall p_{n}\leq p_{n+1}$, $n\geqslant 3$ (because $p_{3}=5$) $\Rightarrow f_{1}(p_{n}) \leq f_{1}(p_{n+1})$ or $$\sqrt{p_{n}} - ln(p_{n}) \leq \sqrt{p_{n+1}} - ln(p_{n+1})$$ Finally: $$0< ln(p_{n+1}) - ln(p_{n}) \leq \sqrt{p_{n+1}} - \sqrt{p_{n}}, \forall n\geq 3$$ As we can see, the analogy isn't of any use really, though we have a nice inequality.

2. The second attempt

Let's have a look at another function: $f_{2}(x)=\frac{x}{ln(x)} - \sqrt{x}$. Its first derivative is ${f_{2}}'(x)=\frac{ln(x)-1}{(ln(x))^{2}}-\frac{1}{2\cdot \sqrt{x}}=\frac{1}{2\cdot \sqrt{x}\cdot (ln(x))^{2}}\cdot \left ( 2\cdot \sqrt{x}\cdot ln(x)-2\cdot \sqrt{x}-(ln(x))^{2} \right )$.

For the first term we have: $\frac{1}{2\cdot \sqrt{x}\cdot (ln(x))^{2}}> 0$, for $\forall x> 0$.

Let's check the second term: $\left ( 2\cdot \sqrt{x}\cdot ln(x)-2\cdot \sqrt{x}-(ln(x))^{2} \right )=$ $\left (-x+2\cdot \sqrt{x}\cdot ln(x)-(ln(x))^{2}-2\cdot \sqrt{x}+x \right )=$ $\left [ -\left ( x-2\cdot \sqrt{x}\cdot ln(x)+(ln(x))^{2} \right ) +\left ( 1- 2\cdot \sqrt{x}+x\right )-1\right ]=$ $\left [ \left ( \sqrt{x}-1\right )^{2}-\left ( \sqrt{x}-ln(x) \right )^{2} -1\right ]$ and we are not done yet. Using $a^{2}-b^{2}=(a-b)\cdot (a+b)$, we have: $\left ( 2\cdot \sqrt{x}\cdot ln(x)-2\cdot \sqrt{x}-(ln(x))^{2} \right )=$ $\left [ \left ( ln(x)-1 \right )\cdot \left ( \sqrt{x}-1+\sqrt{x}-ln(x) \right )-1 \right ]$.

What we have so far:

  • $ln(x)-1 \geq 1$, for $\forall x \geq e^{2}$
  • $\sqrt{x}-1 \geq 1$, for $\forall x \geq 4$
  • $\sqrt{x}-ln(x)>0$, for $\forall x \geq 4$, this is, by the way, $f_{1}(x)$, so $f_{1}(x)\geq f_{1}(4)>0$
Altogether: $\left ( 2\cdot \sqrt{x}\cdot ln(x)-2\cdot \sqrt{x}-(ln(x))^{2} \right )\geq 0$, for $\forall x\geq e^{2}$.

This means ${f_{2}}'(x)\geq 0$ and $f_{2}(x)$ is ascending, for $\forall x\geq e^{2}$. As a result, for $\forall p_{n}\leq p_{n+1}$, $n\geqslant 3$ (the cases for $p_{3}=5$, $p_{4}=7$ and $p_{5}=11$ can be verified with a calculator) $\Rightarrow f_{2}(p_{n}) \leq f_{2}(p_{n+1})$ or $$\frac{p_{n}}{ln(p_{n})} - \sqrt{p_{n}}\leq \frac{p_{n+1}}{ln(p_{n+1})} - \sqrt{p_{n+1}}$$ Final result is (let's note it as (2)): $$ \sqrt{p_{n+1}}- \sqrt{p_{n}}\leq \frac{p_{n+1}}{ln(p_{n+1})} - \frac{p_{n}}{ln(p_{n})}, \forall n\geq 3$$

2.1 A negative result of the second attempt

It is worth mentioning that function $\frac{x}{ln(x)}$ has a special role in the number theory. According to the Prime Number Theorem: $\displaystyle\smash{\lim_{x \to \infty }}\tfrac{\pi (x)}{x/ln(x)}=1$, where $\pi (x)$ is the prime counting function.

Obviously, $\displaystyle\smash{\lim_{n \to \infty }}\tfrac{\pi (p_{n})}{p_{n}/ln(p_{n})}=1$ and $\displaystyle\smash{\lim_{n \to \infty }}\tfrac{\pi (p_{n+1})}{p_{n+1}/ln(p_{n+1})}=1$ (as sub-sequences).

Also $\pi (p_{n})=n$ and $\pi (p_{n+1})-\pi (p_{n})=1$.

If we put all these together, does it mean that $\displaystyle\smash{\lim_{n \to \infty }} \left ( \frac{p_{n+1}}{ln(p_{n+1})} - \frac{p_{n}}{ln(p_{n})} \right )=1$?

Nope, it doesn't, check this link for more details.

2.2 A positive result of the second attempt

According to the following article, in 2005 it was proved that $\displaystyle\smash{\lim_{n \to \infty }}inf \frac{g_{n}}{ln(p_{n})}=0$, where $g_{n}=p_{n+1}-p_{n}$ or the n-th gap.

It is also obvious that $\frac{p_{n+1}}{ln(p_{n+1})} < \frac{p_{n+1}}{ln(p_{n})}$ (because $p_{n} < p_{n+1}$ and $ln(p_{n}) < ln(p_{n+1})$). As a result: $$ \sqrt{p_{n+1}}- \sqrt{p_{n}}\leq \frac{p_{n+1}}{ln(p_{n+1})} - \frac{p_{n}}{ln(p_{n})}\leq \frac{g_{n}}{ln(p_{n})}, \forall n\geq 3$$ Or $$\displaystyle\smash{\lim_{n \to \infty }}inf\left ( \sqrt{p_{n+1}}- \sqrt{p_{n}} \right )=0$$ This means that Andrica's conjecture is true for an infinity pairs of $p_{n}$ and $p_{n+1}$. It doesn't prove the conjecture though, which states "it is true for all $p_{n}$ and $p_{n+1}$"

3. The third attempt

How about the following function $f_{3}(x)=\pi (x) - \frac{x}{ln(x)}$? Well, for this case I used a little Python program, as per below:

import math
import matplotlib.pyplot as plt

cache_prime = {}
cache_prime[1] = False
cache_prime[2] = True
cache_prime[3] = True

def is_prime(n):
    if n in cache_prime:
        return cache_prime[n]

    print "calculate",n
    l = int(math.sqrt(n)) + 1
    for i in xrange(2,l):
        if (n % i) == 0:
            cache_prime[n] = False
            return False
    cache_prime[n] = True
    return True

def p(x):
    ret = 0
    i = 2
    while i <= x:
        if is_prime(i):
            ret += 1
        i += 1
    return ret

def f(x):
    return p(x) - x/math.log(x)
    #return p(x) - math.sqrt(x)

N = 40000
step = 0.25
x = []
y = []
x1 = []
y1 = []

n = START + 1.5
for i in xrange(START, N):
    val = f(n)
    n_n = int(n)
    if (abs(n_n - n) <= 0.0001) and is_prime(n_n):
    n += step

plt.plot(x, y)
plt.plot(x1, y1)
First of all, $f_{3}(23)=1.66463325521 > f_{3}(29)=1.38774807317$. So, $f_{3}(x)$ is not ascending. The general tendency of $f_{3}(x)$ seems to be ascending though, according to this graphic (click to enlarge):
At least, for the areas where the function is ascending for consecutive primes (update the program to plot just plt.plot(x1, y1), i.e. primes and values of the function for the prime arguments), Andrica's conjecture is true, because if $$\pi (p_{n+1}) - \frac{p_{n+1}}{ln(p_{n+1})} \geq \pi (p_{n}) - \frac{p_{n}}{ln(p_{n})}$$ then (also consider (2)) $$1=\pi (p_{n+1}) - \pi (p_{n}) \geq \frac{p_{n+1}}{ln(p_{n+1})} - \frac{p_{n}}{ln(p_{n})}$$Still, this is not the proof.

4. What's next?

Well, probably the next logical thing is to analyse the function $f_{4}(x)=\pi (x) - \sqrt{x}$. At least it seems to be ascending for prime arguments.

But the work is still in progress...