🔢 mathematics

Lines in the prime number graph

This paper investigates the geometric properties of the prime number graph by establishing new upper and lower bounds for the minimum number of line segments required to cover its points and the maximum number of collinear points, including results conditional on the Riemann Hypothesis that refine a recent conjecture by Sloane.

Original authors: Carl Pomerance, Patrick Solé

Published 2026-05-22

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Carl Pomerance, Patrick Solé

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a giant scatter plot on a piece of graph paper. On the horizontal axis (the x-axis), you write down the counting numbers: 1, 2, 3, 4, and so on. On the vertical axis (the y-axis), you write down the corresponding prime numbers: 2, 3, 5, 7, 11, etc.

So, the first point is (1, 2), the second is (2, 3), the third is (3, 5), and so on. This collection of dots is what mathematicians call the Prime Number Graph.

This paper, written by Carl Pomerance and Patrick Solé, asks two fun questions about these dots:

The "String" Question: If you wanted to connect all the first $n$ dots using the fewest possible straight lines (like drawing with a ruler), how many lines would you need? They call this number $L(n)$ .
The "Crowded Line" Question: What is the maximum number of dots you can find that all sit perfectly on a single straight line? They call this number $B(n)$ .

The Big Picture: Why is this hard?

Prime numbers are a bit like a sparse crowd at a huge party. They get further and further apart as the numbers get bigger. Because they are so spread out, it's impossible to draw one single line that hits every prime number forever. Eventually, the line will miss the next dot.

The authors are trying to figure out the rules of this game for very large numbers.

Question 1: How many lines do we need? ( $L(n)$ )

Imagine you are trying to cover a trail of stepping stones (the prime points) with planks of wood (straight lines). You want to use as few planks as possible.

The Old Guess: A mathematician named Sloane guessed that the number of planks needed grows very slowly, roughly like the number of stones divided by the natural log of that number.
The New Result: The authors didn't quite prove Sloane's guess was exactly right, but they got very close. They proved that the number of lines needed is roughly proportional to the number of points, divided by the log of the number, but with a tiny extra "fuzziness" factor (mathematically written as $n \log \log n / \log n$ ).
The "Awkward" Primes: The paper also talks about "awkward" primes. These are the specific points where you have to add a new line because the current lines can't reach them. The authors prove that these awkward moments happen, but they become rare enough that if you added up the "reciprocals" (1 divided by the number) of all these awkward primes, the total sum would be a finite number.

Question 2: How many dots can fit on one line? ( $B(n)$ )

Now, imagine you are looking for the "hottest" line on your graph—the one that hits the most dots.

The Lower Bound (The Minimum Guarantee): The authors proved that no matter how far out you go, you can always find a line that hits at least a certain number of dots. Specifically, for a large number of points $n$ , you can guarantee finding a line that hits at least a tiny fraction of the logarithm of $n$ dots. Think of it as finding a "lucky streak" of dots that happen to line up.
The Upper Bound (The Limit): They also proved that you can't find too many dots on a single line. The number of dots on the best line is limited by how "wiggly" the prime numbers are.
The "Riemann Hypothesis" Twist: There is a famous, unsolved math mystery called the Riemann Hypothesis (RH). It's like a "super-accurate" rulebook for how prime numbers are distributed.
- If we assume RH is true: The authors can give much tighter limits. They show that under this assumption, the "crowded line" can't have more than about $n^{3/4}$ dots (roughly the square root of the square root of $n$ , multiplied by some factors).
- The Consequence: If the line can't be too crowded, it means you need more lines to cover everything. So, under RH, the minimum number of lines ( $L(n)$ ) must be at least a certain size (roughly $n^{1/4}$ ).

The Tools They Used

To solve this, the authors didn't just guess; they used a powerful mathematical tool called the Prime Number Theorem with Remainder.

Think of the Prime Number Theorem as a very good map that predicts where the prime numbers should be. The "remainder" part is the error margin on that map. The authors used a very precise map (with a tiny error margin) to draw "parallelograms" (slanted boxes) around the dots. They showed that if you draw lines with specific slopes (based on a mathematical sequence called the Farey sequence), these lines will catch a lot of the dots inside those boxes.

The Conclusion

The paper wraps up by saying:

We have a good upper limit on how many lines we need to cover the primes.
We have a good lower limit on how many primes can sit on one line.
However, there is still a "gap" between the best possible answer and the answer we can currently prove. The authors admit their estimates aren't perfect yet and that there is still work to be done to close the gap between the "minimum lines needed" and the "maximum dots on a line."

In short, they've built a better fence around the problem, but they haven't quite found the exact shape of the garden inside yet.

Technical Summary: Lines in the Prime Number Graph

Problem Statement
The paper investigates the geometric properties of the "prime number graph," defined as the set of points $(n, p_n)$ in the plane, where $p_n$ is the $n$ -th prime number. The central focus is on two specific functions:

$L(n)$ : The minimum number of straight line segments required to cover the first $n$ prime points.
$B(n)$ : The maximum number of prime points $(k, p_k)$ with $k \le n$ that can be covered by a single straight line.

The study is motivated by recent numerical observations and a conjecture by Sloane, who proposed that $L(n) = O(n / \log n)$ . The authors aim to provide rigorous asymptotic bounds for these functions using analytic number theory, specifically the Prime Number Theorem (PNT) with remainder terms.

Methodology
The authors employ a combination of combinatorial arguments and deep results from analytic number theory.

Farey Sequences and Interval Dissection: To bound $L(n)$ , the authors utilize the Farey sequence of level $k$ . They dissect the interval $(e^k, e^{k+1}]$ based on consecutive terms $a/b$ and $a'/b'$ of the Farey sequence. This allows them to construct specific intervals $I = (u, u']$ where the slope of lines approximating the prime distribution is controlled.
Prime Number Theorem with Remainder: The proofs rely heavily on the error term in the approximation of the prime-counting function $\pi(x)$ by the logarithmic integral $\text{li}(x)$ . The authors use the unconditional bound $|\pi(x) - \text{li}(x)| \le x \exp(-c(\log x)^{3/5}(\log \log x)^{-1/5})$ and the conditional bound under the Riemann Hypothesis (RH), $|\pi(x) - \text{li}(x)| \le x^{1/2} \log x$ .
Geometric Constraints: To bound $B(n)$ , the authors analyze the intersection of a straight line with the region defined by $|y - \text{li}(x)| \le R(x)$ , where $R(x)$ represents the error bound. By leveraging the concavity of $\text{li}(x) \pm R(x)$ , they determine the maximum number of times a line can intersect this region, thereby limiting the number of prime points a single line can cover.
Combinatorial Relation: A fundamental inequality $L(n)B(n) \ge n$ is used to derive lower bounds for one function based on upper bounds for the other.

Key Contributions and Results

Upper Bound for $L(n)$ :
The authors prove that $L(n) = O\left(\frac{n \log \log n}{\log n}\right)$ . This result comes close to Sloane's conjecture of $O(n / \log n)$ but includes an additional $\log \log n$ factor. The proof involves summing the number of lattice lines required to cover inverse prime points $(p_n, n)$ across intervals defined by Farey dissections.
Lower Bound for $B(n)$ :
It is established that $B(n) \ge c \log n$ for some constant $c > 0$ and all sufficiently large $n$ . This is derived by analyzing the average number of points per line in the specific interval $(e^k, e^{k+1/k}]$ used in the $L(n)$ proof.
Conditional Results under the Riemann Hypothesis (RH):
Assuming RH, the authors provide tighter bounds:
- $B(n) = O(n^{3/4} (\log n)^{1/2})$ .
- $L(n) \ge c' n^{1/4} (\log n)^{-1/2}$ for some constant $c' > 0$ .
  These results highlight the gap between the unconditional lower bound for $L(n)$ and the conditional upper bound for $B(n)$ , and vice versa.
Awkward Primes:
The paper defines an "awkward prime" $p_n$ as one for which $L(n) > L(n-1)$ . The authors prove that the number of such primes up to $n$ is exactly $L(n)$ . Consequently, the reciprocal sum of awkward primes is finite, as the counting function is $O(\pi(x) \log \log x / \log x)$ .

Significance and Limitations
The paper provides the first rigorous asymptotic bounds for the covering number $L(n)$ and the collinearity number $B(n)$ in the prime number graph. The authors explicitly state that their estimates "seem far from optimal," noting a significant gap between their derived bounds and the conjectured values (e.g., between Theorem 3 and Corollary 2 for $L(n)$ , and between Theorem 5 and Corollary 2 for $B(n)$ ).

The work serves to formalize numerical observations found in previous literature (such as [5] and [6]) and connects the geometric distribution of primes to the error terms of the Prime Number Theorem. The authors conclude by identifying the reduction of the gaps between their upper and lower bounds as a challenging open problem for future research.

The Big Picture: Why is this hard?

Question 1: How many lines do we need? (L(n)L(n)L(n))

Question 2: How many dots can fit on one line? (B(n)B(n)B(n))

The Tools They Used

The Conclusion

Technical Summary: Lines in the Prime Number Graph

More like this

Question 1: How many lines do we need? ( $L(n)$ )

Question 2: How many dots can fit on one line? ( $B(n)$ )