🔢 mathematics

The Primes are $2$-Accessible

This paper proves that the set of positive integers with between 1 and $n$ prime factors (counted with multiplicity) has a degree of accessibility of $2^n$ , thereby confirming that the set of prime numbers is $2$-accessible and answering a question posed by Landman and Robertson.

Original authors: Oscar Quester

Published 2026-06-02

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Oscar Quester

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

The Big Picture: A Game of Color and Distance

Imagine you have an infinite line of stepping stones, numbered 1, 2, 3, and so on, stretching forever. You are playing a game where you paint every stone with one of several colors (say, Red, Blue, or Green).

The question mathematicians ask is: No matter how you paint the stones, can you always find a long, straight path of stones that are all the same color, where the distance between each step follows a specific rule?

In this paper, the "rule" for the distance is based on Prime Numbers (2, 3, 5, 7, 11...).

If you step 2 stones, that's a prime.
If you step 3 stones, that's a prime.
If you step 6 stones, that's not a prime (it's 2 times 3), but it is made of primes.

The paper answers a specific question: If you use only 2 colors, can you always find a long, same-colored path where the steps are prime numbers?

The answer is YES. The author proves that the set of prime numbers is "2-accessible." This means that even if a mischievous painter tries to hide long, same-colored paths using only two colors, they will fail. You can always find a long chain of same-colored stones where the gaps between them are prime numbers.

Key Concepts Explained

1. The "Accessibility" Score

Think of "accessibility" as a difficulty rating for a game.

1-accessible: If you have 1 color, you can obviously find a long path (everything is the same color).
2-accessible: If you have 2 colors, you can still find a long path.
3-accessible: If you have 3 colors, you can find a long path.

The paper proves that for Prime Numbers, the difficulty rating is exactly 2.

If you use 2 colors, you can always find the path.
If you use 3 colors, the painter can arrange the colors so that no long path exists. (The paper mentions this was already known, but the new discovery is that 2 colors isn't enough to stop the path).

2. The "Super-Set" of Numbers

The paper doesn't just look at single primes (2, 3, 5). It looks at groups of numbers formed by multiplying primes together.

Group 1: Just the primes (2, 3, 5...).
Group 2: Primes and products of two primes (2, 3, 5, 4, 6, 9, 10...).
Group n: Numbers made of up to $n$ prime factors.

The author proves a general rule:

If you look at numbers made of up to $n$ prime factors, the "accessibility score" is $2n$ .
So, for just primes ( $n=1$ ), the score is $2 \times 1 = 2$ .
For numbers made of up to 2 primes ( $n=2$ ), the score is $2 \times 2 = 4$ .

How the Proof Works (The Analogy)

The author uses a clever strategy to prove that you can't hide the path when using 2 colors. Imagine you are looking for a pattern in a chaotic crowd.

Step 1: The "Gap" Strategy
The author looks at the "gaps" between stones of the same color.

Scenario A (The Gaps are Wild): If the gaps between same-colored stones are huge and unpredictable, the author shows that this chaos actually forces a long, straight line to appear. It's like if people in a crowd are standing so far apart that they accidentally line up perfectly.
Scenario B (The Gaps are Tight): If the gaps are small and regular, the same-colored stones are packed together. The author then uses a powerful mathematical tool (called a "density recurrence theorem") which says that if a group of numbers is packed tightly enough, it must contain a specific, repeating pattern.

Step 2: The "Grid" Trick
In the "tight gap" scenario, the author finds a two-dimensional grid of same-colored numbers. From this grid, they can extract a long, straight line where the steps are exactly the prime numbers (or multiples of them) they were looking for.

The "Impossible" 3-Color Trick

To prove that 2 is the maximum score (and that 3 colors would break the pattern), the author constructs a specific, tricky painting scheme.
Imagine a repeating pattern of colors that is designed specifically to break any long chain of prime steps.

The author creates a pattern where the "distance" between same-colored stones is always a multiple of a large number.
However, prime numbers (and their small multiples) are "too small" or "too weird" to fit into this rigid pattern without breaking the color rule.
This proves that with 3 colors, a clever painter can stop you from finding a long path.

Summary of Results

The Main Discovery: The set of prime numbers is 2-accessible. No matter how you paint the integers with 2 colors, you will always find arbitrarily long sequences of the same color where the steps are prime numbers.
The General Rule: If you expand the game to include numbers made of up to $n$ prime factors, the game becomes harder. You need $2n$ colors to successfully hide the path. With fewer than $2n$ colors, the path will always be found.
The Method: The proof combines a "pigeonhole" argument (if you have too many items and too few boxes, some boxes must be crowded) with advanced theorems about how numbers repeat in dense groups.

What This Means (and Doesn't Mean)

What it means: It solves a specific math puzzle that Landman and Robertson asked years ago. It confirms that prime numbers have a very strong "Ramsey property"—they are so fundamental that they force order to appear, even in a chaotic, 2-colored world.
What it doesn't mean: The paper does not discuss using this for cryptography, computer security, or physics. It is a pure mathematics result about the structure of numbers and patterns.

In a nutshell: The primes are stubborn. You can try to paint the number line with two colors to hide them, but the primes are so deeply woven into the fabric of numbers that they will always reveal a long, same-colored path.

Technical Summary: "The Primes Are 2-Accessible"

Problem Statement
This paper addresses a question in Ramsey theory concerning the "accessibility" of sets of integers. Specifically, it investigates the set of prime numbers, $P = \{2, 3, 5, \dots\}$ . A set $D \subseteq \mathbb{N}$ is defined as $r$ -accessible if, for every $r$ -coloring of the natural numbers, there exist arbitrarily long monochromatic sequences $x_1, \dots, x_k$ such that the differences $x_{i+1} - x_i$ belong to $D$ . The degree of accessibility, denoted $doa(D)$, is the largest integer $r$ for which $D$ is $r$ -accessible.

Prior work by Landman and Robertson established that the primes are not 3-accessible (via a periodic 3-coloring) and that shifted primes $P+c$ are 2-accessible for every odd $c$ . However, the 2-accessibility of the unshifted primes $P$ remained an open question (Question 7 in [6] and Research Question 10.2 in [7]). The paper also seeks to determine the degree of accessibility for the set $P(n)$ , defined as the set of positive integers with between 1 and $n$ prime factors (counted with multiplicity).

Methodology
The author employs a combination of combinatorial arguments and deep results from ergodic theory and additive number theory.

Density Recurrence and Szemerédi-type Theorems: The core of the proof relies on a theorem by Frantzikinakis, Host, and Kra [4], which establishes that the shifted primes $P-1$ and $P+1$ are sets of density recurrence. This means that for any set $A$ with positive upper Banach density, the set of recurrence times intersects both $P-1$ and $P+1$ .
Iterative Density Argument: A key lemma (Lemma 1) is derived to show that if $E_1, \dots, E_n$ are sets of density recurrence, one can construct a multi-dimensional grid within a set of positive density using elements from these sets.
Case Analysis on Gaps: The proof of the main theorem (Theorem 1) analyzes an arbitrary $N$ $N$ -coloring of $\mathbb{N}$ $N$ by examining the set $X$ $X$ of starting points of monochromatic pairs with distances in $\{1, \dots, N-1\}$ ${1, \dots, N - 1}$ .
- Case 1 (Unbounded Gaps): If $X$ has unbounded gaps, a pigeonhole argument forces the existence of long monochromatic arithmetic progressions with common difference $N$ . Since $N$ can be factored into a prime and a coefficient $\le N-1$ , these progressions form valid diffsequences.
- Case 2 (Bounded Gaps): If $X$ has bounded gaps, it has positive upper Banach density. The author applies the density recurrence of $P-1$ and $P+1$ to find a two-dimensional grid structure within a monochromatic subset. From this grid, a long monochromatic diffsequence with differences in the target set is extracted.
Construction of Counterexamples: To establish upper bounds on accessibility, the paper constructs specific periodic colorings. For the set $D_N = \bigcup_{t=1}^{N-1} tP$ , an $(N+1)$ -coloring is defined using modular arithmetic and a carefully constructed set $B$ to prevent arbitrarily long monochromatic diffsequences.

Key Contributions and Results

Theorem 1: For any integer $N \ge 2$ $N \geq 2$ , the degree of accessibility of the set $D_N = \bigcup_{t=1}^{N-1} tP$ $D_{N} = ⋃_{t = 1}^{N - 1} tP$ is exactly $N$ $N$ .
- Corollary: By setting $N=2$ , the set $1 \cdot P = P$ is 2-accessible. This definitively answers the open question regarding the 2-accessibility of the primes.
Theorem 2: For every $n \ge 1$ $n \geq 1$ , the degree of accessibility of the set $P(n)$ $P (n)$ (integers with $1 \le k \le n$ $1 \leq k \leq n$ prime factors) is exactly $2n$ $2 n$ .
- This generalizes the result for primes ( $n=1 \implies doa(P)=2$ ).
Proof of Non-Accessibility: The paper provides explicit constructions showing that $P(n)$ is not $(2n+1)$ -accessible, utilizing a generalization of the coloring used by Landman and Robertson to show $P$ is not 3-accessible.

Significance
The paper resolves a specific open problem posed by Landman and Robertson regarding the 2-accessibility of the prime numbers. By proving that $doa(P) = 2$, it confirms that while the primes cannot support arbitrarily long monochromatic sequences under a 3-coloring, they do so under any 2-coloring.

Furthermore, the work extends this understanding to the broader class of sets $P(n)$ , establishing a precise formula for their degree of accessibility ( $2n$ ). The methodology demonstrates the utility of applying polynomial Szemerédi-type theorems for shifted primes (specifically the recurrence properties of $P-1$ and $P+1$ ) to solve classical Ramsey-theoretic problems concerning the structure of the primes. The paper concludes by posing two open questions: whether $P+c$ is 2-accessible for even $c$ , and for which sets $D$ the relation $doa(D(n)) = (doa(D))^n$ holds.