Lines in the prime number graph

Abstract

The prime number graph is the set of points $(n,p_n)$ where $p_n$ denotes the $n^{\mathrm{th}}$ prime. Let $L(n)$ be the minimum number of straight line segments needed to cover the first $n$ points in this set. Let $B(n)$ be the largest number of points $(k,p_k)$ with $k\le n$ covered by a single line. Recently Sloane conjectured that $L(n)=O(n/\log n)$. We show that $L(n)=O(n\log \log n/\log n)$ and $B(n)\ge c\log n$ for a constant $c>0$ and all large $n$. Under RH we show that for large $n$ we have $B(n)=O(n^{3/4}(\log n{)}^{1/2})$ and $L(n)\ge c^{\prime }{n}^{1/4}(\log n{)}^{-1/2}$ for some constant $c^{\prime }>0.$

8 pages