Sunday, November 11, 2012

Tackling Andrica's conjecture. Part 2

With the previous post, I stopped at the argument that $f_{4}(x)=\pi (x) - \sqrt{x}$ seems to be ascending for prime arguments. Apparently, this is a necessary and sufficient condition, i.e.:
Lemma 1. Andrica's conjecture is true iff function $f_{4}(x)=\pi (x) - \sqrt{x}$ is strictly ascending ($x < y \Rightarrow f(x) < f(y)$) for prime arguments.
The proof is given in the following discussion with the math.stackexchange.com community.
It is worth mentioning that $f_{4}(x)$ is descending in between prime numbers. For example for $\forall x\in \left ( p_{n}, p_{n+1} \right )$, $f_{4}(x)=n - \sqrt{x}$ and ${f_{4}}'(x)=-\frac{1}{2\cdot \sqrt{x}} < 0$.
In fact the purpose of the discussion was to prove that $$\sqrt{p_{n}} < n$$ which turns to be true for $\forall n \geq 2$, using Rosser's theorem.
Interesting result, out of this inequality, is that $$\sqrt{p_{n}} - \sqrt{p_{1}} < n-1$$ because $\sqrt{p_{1}}=\sqrt{2} > 1$. However, $$\sum_{k=2}^{n}\left ( \sqrt{p_{k}} - \sqrt{p_{k-1}} \right )=\sqrt{p_{n}} - \sqrt{p_{1}} < n-1$$ and as a result $$\frac{1}{n-1}\cdot \sum_{k=2}^{n}\left ( \sqrt{p_{k}} - \sqrt{p_{k-1}} \right ) < 1$$ or, in other words, on average Andrica's conjecture seems to be true.
But, leaving the statistical argument aside, how do we prove that $f_{4}(x)$ is ascending for prime arguments?
I don't have the answer yet, but here is where I stuck ...
Let's have a look at the following function $$f_{5}(x)=1 - \sqrt{p_{n+1} + x} + \sqrt{p_{n} + x}$$ This function is ascending $\forall x \geq -p_{n}$ $${f_{5}(x)}'= -\frac{1}{2\cdot \sqrt{p_{n+1} + x}} + \frac{1}{2\cdot \sqrt{p_{n} + x}} > 0$$ because $\sqrt{p_{n+1} + x} > \sqrt{p_{n} + x}$, for $\forall x \geq -p_{n}$.
This function also has a zero, $1=\sqrt{p_{n+1} + x} - \sqrt{p_{n} + x} \Leftrightarrow $ $$1 = p_{n+1}+p_{n} +2\cdot x -2\cdot \sqrt{(p_{n+1} + x)\cdot (p_{n} + x)} \Leftrightarrow $$ $$2\cdot \sqrt{(p_{n+1} + x)\cdot (p_{n} + x)}=p_{n+1}+p_{n} +2\cdot x - 1 \Leftrightarrow $$ $$4\cdot (p_{n+1} + x)\cdot (p_{n} + x)=p_{n+1}^{2}+p_{n}^{2}+4\cdot x^{2}+1+2\cdot p_{n+1}\cdot p_{n}+$$ $$+4\cdot p_{n+1}\cdot x-2\cdot p_{n+1}+4\cdot p_{n}\cdot x-2\cdot p_{n}-4\cdot x \Leftrightarrow $$ jumping ahead $$2\cdot p_{n+1}\cdot p_{n}=p_{n+1}^{2}+p_{n}^{2}+1-2\cdot p_{n+1}-2\cdot p_{n}-4\cdot x \Leftrightarrow $$ $$4\cdot x=(p_{n+1}-p_{n})^{2}-2\cdot (p_{n+1}+p_{n})+1=(p_{n+1}-p_{n}-1)^{2}-4\cdot p_{n}$$ as a result $$x_{0}=\left( \frac{p_{n+1}-p_{n}-1}{2} \right)^{2}-p_{n}$$ Obviously, $x_{0} > -p_{n}$.
And now:
Lemma 2. $f_{4}(p_{n+1}) > f_{4}(p_{n})$ iff $x_{0} < 0$, where $x_{0}$ is zero of $f_{5}(x)$.
First of all $$x_{0} < 0 \Leftrightarrow p_{n+1}-p_{n} < 2\cdot \sqrt{p_{n}}+1$$
As a result, if $f_{4}(p_{n+1}) > f_{4}(p_{n})$ this is equivalent (from Lemma 1) with $\sqrt{p_{n+1}}-\sqrt{p_{n}} < 1$ (Andrica's inequality for $p_{n}, p_{n+1}$). But then $$p_{n+1} - p_{n}=(\sqrt{p_{n+1}}-\sqrt{p_{n}})\cdot (\sqrt{p_{n+1}}+\sqrt{p_{n}}) < \sqrt{p_{n+1}}+\sqrt{p_{n}}$$ and applying Andrica's inequality again $$p_{n+1} - p_{n} < \sqrt{p_{n}}+1+\sqrt{p_{n}}=2\cdot \sqrt{p_{n}}+1$$ so $x_{0} < 0$.
Now, if $x_{0} < 0$, where we know that $x_{0} > -p_{n}$, and the fact that $f_{5}(x)$ is ascending then we have $$x_{0} < 0 \Rightarrow 0=f_{5}(x_{0}) < f_{5}(0)=1 - \sqrt{p_{n+1}} + \sqrt{p_{n}}$$ or $$\sqrt{p_{n+1}}-\sqrt{p_{n}} < 1$$ and then (Lemma 1) $f_{4}(p_{n+1}) > f_{4}(p_{n})$.
Do we know if $p_{n+1}-p_{n} < 2\cdot \sqrt{p_{n}}+1$ for $\forall n$?
Not yet, but we are close. One result, proved by Martin Huxley, states that $p_{n+1}-p_{n} < p_{n}^{\theta }$ for $\theta > \frac{7}{12}$ and sufficiently large $n$. In our case, $\theta =0.5$
Another result by Baker, Harman and Pintz states that $\theta$ may be taken to be 0.525.