🔢 mathematics

Folkman's theorem and the primes

This paper presents two new proofs of the infinitude of prime numbers by applying Folkman's theorem (or equivalently, Hindman's theorem) from additive Ramsey theory.

Original authors: David J. Fernández-Bretón

Published 2026-04-22

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: David J. Fernández-Bretón

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 are trying to prove that there are an infinite number of prime numbers (numbers like 2, 3, 5, 7, 11 that can only be divided by 1 and themselves).

For over 2,000 years, mathematicians have known this is true. The most famous proof is by Euclid, which is like a simple magic trick: "If you list all the primes, multiply them together, and add 1, you get a new number that isn't divisible by any of them, so there must be a new prime."

But recently, a new wave of mathematicians has been asking: "Can we prove this using a completely different kind of math?" Specifically, they are using Ramsey Theory.

What is Ramsey Theory? (The "Party" Analogy)

Think of Ramsey Theory as the study of order in chaos. It says that if you have a big enough group of things, you can't help but find some pattern.

The Classic Example: If you invite 6 people to a party, you are guaranteed to find either 3 people who all know each other, or 3 people who are all strangers. You can't avoid it.
Folkman's Theorem (The Star of This Paper): This is a super-powerful version of that idea. Imagine you have a giant bag of numbers. You paint every number with one of a few colors (say, Red, Blue, Green). Folkman's Theorem says: No matter how you paint them, if you pick a big enough group of numbers, you can find a special subset where every possible sum you can make from them is the same color.

It's like saying: "If you have enough people in a room, you can always find a group where every possible combination of handshakes results in the same color of handshake."

The Paper's Goal

The author, David Fernández-Bretón, wants to use this "coloring" trick to prove that primes are infinite. He says: "Let's pretend there are only a finite number of primes. If we can show that this leads to a logical contradiction using Folkman's Theorem, then our assumption was wrong, and there must be infinite primes."

He provides two different ways to do this.

Proof #1: The "Unique Fingerprint" Strategy

The Setup:
Imagine we have a finite list of all the primes. We take every number in the universe and give it a "fingerprint" based on how many times each prime divides it.

For example, the number 12 is $2^2 \times 3^1$ . Its fingerprint tells us it has two 2s and one 3.

The Trick:

We paint every number based on its fingerprint (specifically, the "parity" or even/odd nature of these counts).
We use Folkman's Theorem to find a special group of numbers ( $X$ ) where every sum you make from them has the exact same fingerprint color.
The Contradiction: The author shows that if you have enough numbers in this group, you can pick two different numbers, add them, and the "fingerprint" of the result must change (because of how addition works with prime factors).
But Folkman's Theorem said the color (fingerprint) cannot change!
Conclusion: Since we reached a contradiction, our starting idea (that there are only a finite number of primes) must be false. There are infinite primes.

Analogy: Imagine you have a box of Legos. You claim there are only 5 types of bricks. You try to build a tower where every time you add a brick, the color of the tower stays exactly the same. But the laws of physics (math) say that if you add a specific brick, the color must change. Since the tower didn't change color, your claim that there were only 5 brick types was wrong.

Proof #2: The "Crowded Room" Strategy

The Setup:
This proof is a bit more aggressive. It uses a much larger group of numbers to ensure the "pigeonhole principle" (if you have more pigeons than holes, at least one hole has two pigeons) works in our favor.

The Trick:

We assume there are only $N$ primes.
We create a massive group of numbers ( $M$ ) and paint them based on their prime factors.
Folkman's Theorem guarantees a "monochromatic" group where all sums look the same.
The Squeeze: The author argues that this group is so huge that it's "too crowded." Even if we try to filter out duplicates, there are still too many numbers left.
By carefully picking a few numbers from this crowded group and adding them up, we force a situation where the math breaks down (similar to Proof #1). The "sum" ends up being equal to one of the original numbers, which is impossible unless the number is zero (but we started with positive numbers).

Analogy: Imagine a crowded dance floor. You claim there are only 3 types of shoes. You try to find a group of dancers where, no matter who pairs up to dance, they all wear the same shoe color. The author says, "The floor is so crowded that eventually, two people with the same shoe color will pair up, and their combined 'shoe energy' will create a new shoe color. But the rules said the color couldn't change! Therefore, there must be more than 3 types of shoes."

Why Does This Matter?

You might ask, "Euclid's proof is simple. Why do we need these complicated Ramsey proofs?"

New Perspectives: It shows that the infinitude of primes is connected to deep patterns in how numbers combine. It's like discovering that the reason the sky is blue is connected to the way music harmonizes.
Simplicity of Tools: Surprisingly, these proofs don't use "hard" number theory (like complex formulas about prime distribution). They mostly use combinatorics (counting and logic) and the Pigeonhole Principle.
The Trade-off: The author admits these proofs are "heavier" than Euclid's. Euclid uses a tiny hammer; these proofs use a sledgehammer to crack a nut. But the sledgehammer is interesting because it's made of a different material (Ramsey Theory) than the hammer.

Summary

The paper says: "If you assume there are only a finite number of primes, you can paint the number line in a way that creates a logical paradox when you try to add numbers together. Since the paradox is impossible, the assumption must be wrong. Therefore, primes go on forever."

It's a beautiful demonstration that even the most fundamental truths of math can be viewed through the lens of patterns, colors, and order.

1. Problem Statement

The paper addresses the classical number-theoretic problem of proving the infinitude of prime numbers. While Euclid's proof is the standard, there is a growing research trend (cited in the introduction) to derive this result using Ramsey-theoretic results. Previous proofs in this vein have utilized:

Van der Waerden's theorem (Alpoge).
Schur's theorem combined with Fermat's Last Theorem (Gasarch, Elsholtz).
Roth's theorem and Hindman's theorem (Elsholtz).

The specific gap this paper fills is the application of Folkman's Theorem (a generalization of Schur's theorem and a finite version of Hindman's theorem) to prove the infinitude of primes. The author aims to confirm a conjecture by Elsholtz that Folkman's theorem could be used for this purpose, while attempting to avoid deep number-theoretic machinery (like Fermat's Last Theorem) in favor of combinatorial arguments.

2. Methodology

The author employs a proof by contradiction. The core methodology involves:

Assumption: Assume the set of prime numbers $P$ is finite, with cardinality $|P| = N$ .
Coloring Construction: Define a specific coloring function $c(n)$ $c (n)$ on the natural numbers based on the $p$ -adic valuation ( $\nu_p(n)$ $ν_{p} (n)$ ) and the $p$ -adic unit part ( $\xi_p(n)$ $ξ_{p} (n)$ ) of integers.
- $\nu_p(n)$ : The exponent of prime $p$ in the prime factorization of $n$ .
- $\xi_p(n)$ : The part of $n$ coprime to $p$ (i.e., $n = p^{\nu_p(n)} \xi_p(n)$ ).
Application of Folkman's Theorem:
- Folkman's Theorem: For any finite coloring of $\mathbb{N}$ and any integer $M$ , there exists a set $X \subset \mathbb{N}$ of size $M$ such that the set of all finite sums of distinct elements of $X$ , denoted $FS(X)$, is monochromatic.
- The author applies this theorem to obtain a large monochromatic set $X$ .
Deriving Contradictions: By analyzing the properties of the sums in $FS(X)$ under the specific coloring, the author demonstrates that the assumption of a finite set of primes leads to logical contradictions regarding the $p$ -adic valuations of the sums.

The paper presents two distinct proofs using this framework:

Proof 1: Direct Valuation Contradiction

Coloring: $c(n) = (\nu_2(n) \pmod 2, \xi_2(n) \pmod 4) \frown (\xi_p(n) \pmod p)_{p \in P \setminus \{2\}}$ .
Mechanism:
- Selects a set $X$ of size $N+1$ .
- Claim 1 & 2: Proves that for any distinct $a, b \in X$ $a, b \in X$ , $\nu_p(a) \neq \nu_p(b)$ $ν_{p} (a) \neq = ν_{p} (b)$ for all $p \in P$ $p \in P$ .
  - For $p=2$ : If valuations were equal, the sum $a+b$ would have a different parity of valuation than the elements, violating monochromaticity.
  - For odd $p$ : If valuations were equal, the sum of the unit parts would shift the residue modulo $p$ , violating monochromaticity.
- Contradiction: Since $|X| = N+1$ but there are only $N$ primes, the author constructs a specific sum of a subset of $X$ and adds another element from $X$ . The construction ensures that the valuation of the sum remains unchanged for all primes, implying the added element is zero, which contradicts the fact that $X$ contains non-zero integers.

Proof 2: Pigeonhole Principle and Thinning

Coloring: Simpler coloring $c(n) = (\nu_p(n) \pmod 2)_{p \in P}$ .
Mechanism:
- Selects a much larger set $X$ of size $M = (N+1) \prod_{p \in P} p^4$ .
- Claim 3: Uses the Pigeonhole Principle to show that within $X$ , no more than $p^4$ elements can share the same $\nu_p$ value and the same residue of $\xi_p(n) \pmod{p^2}$ .
- Thinning Process: The author "thins" the set $X$ by removing elements that share $\nu_p$ values, ensuring the remaining subset $Z$ has the property that all elements have distinct $\nu_p$ values for every $p$ .
- Contradiction: Similar to Proof 1, the size of $Z$ is guaranteed to be at least $N+1$ . A specific sum is constructed that leads to the conclusion that a non-zero element must be zero.

3. Key Contributions

Confirmation of Conjecture: The paper confirms Elsholtz's conjecture that Folkman's Theorem can be used to prove the infinitude of primes.
Avoidance of Deep Number Theory: Unlike Gasarch's proof (which uses Fermat's Last Theorem) or Granville's proof (which uses sums of squares), these proofs rely only on combinatorics (Folkman's Theorem and the Pigeonhole Principle). The most advanced number-theoretic tool used is the fundamental property of $p$ -adic valuations regarding sums ( $\nu_p(a+b) = \min(\nu_p(a), \nu_p(b))$ when valuations differ).
Novelty of Proofs: The author provides two distinct proofs. The second proof is noted to be structurally similar to Alpoge's proof using Van der Waerden's theorem but utilizes a different combinatorial engine.
Complexity Analysis: The author notes that while Folkman's theorem is stronger than Schur's theorem, its proof (via ultrafilters or elementary methods) is arguably less complex than the proof of Van der Waerden's theorem, making these proofs "simpler" in a specific technical sense compared to Alpoge's or Granville's approaches, though more complex than Euclid's.

4. Results

Theorem: The set of prime numbers is infinite.
Logical Flow:
1. Assume primes are finite ( $P = \{p_1, \dots, p_N\}$ ).
2. Construct a finite coloring of $\mathbb{N}$ based on $p$ -adic properties.
3. Invoke Folkman's Theorem to find a monochromatic set $X$ of size $N+1$ .
4. Show that the monochromatic property forces distinct elements in $X$ to have distinct $p$ -adic valuations for all $p$ .
5. Demonstrate that with $N+1$ elements and only $N$ primes, one can form a sum that implies a non-zero integer is zero.
6. Conclude the assumption is false; thus, there are infinitely many primes.

5. Significance

Interdisciplinary Bridge: The paper strengthens the connection between Ramsey Theory (combinatorics) and Analytic/Algebraic Number Theory. It demonstrates that deep structural results in combinatorics can replace traditional number-theoretic arguments in fundamental proofs.
Pedagogical Value: It offers a new perspective on the infinitude of primes that highlights the power of partition regularity and monochromatic sets.
Methodological Innovation: By showing that one can avoid "heavy" number-theoretic theorems (like FLT) in favor of combinatorial theorems (Folkman/Hindman), it opens avenues for proving other number-theoretic facts using purely combinatorial tools.
Contextualization: It places the author's work within a specific lineage of recent research (Alpoge, Granville, Gasarch, Elsholtz, Goral, Adıbelli) dedicated to re-proving Euclid's theorem via Ramsey theory, adding a crucial piece (Folkman's theorem) to this collection.

In summary, Fernández-Bretón successfully demonstrates that Folkman's Theorem is a sufficient and powerful tool to derive the infinitude of primes, providing two rigorous proofs that rely on combinatorial logic rather than advanced number theory.