💻 computer science

The set of primes is supernatural: a Lean formalization of the statement of the conjecture

This paper presents a complete, machine-checked Lean 4 formalization of the conjecture that no non-constant function constructed from identity, constants, and finitely many pointwise operations (addition, multiplication, exponentiation) maps every positive integer to a prime, thereby transforming the conjecture into a precise, kernel-verifiable target for automated reasoning systems.

Original authors: A. Mayeux

Published 2026-08-11

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: A. Mayeux

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 a vast, infinite library where every book is a number. In this library, there is a very special, exclusive club called the "Primes." These are numbers that can't be built by multiplying smaller numbers together; they are the indivisible atoms of arithmetic, like 2, 3, 5, or 7. For centuries, mathematicians have tried to write a single, simple recipe—a machine made of basic math tools—that could spit out only these special club members. They wanted a machine that, no matter what number you fed it, would always output a Prime.

The tools allowed in this recipe are the most basic ones we know: adding numbers together, multiplying them, and raising them to powers (like squaring or cubing). You can mix and match these tools as much as you like, but you can't use anything fancy like division or square roots. The big question is: Is there a way to build a machine using only these simple tools that never makes a mistake? Could such a machine generate a never-ending list of primes, or will it eventually stumble and produce a number that isn't prime? This isn't just a game; it touches the very heart of how numbers are structured. If such a machine existed, it would mean the primes follow a simple, predictable pattern. If not, it means the primes are wild, chaotic, and "supernatural" in a way that defies simple formulas.

This paper is a digital detective story about that very question. The author, Arnaud Mayeux, has taken a specific mathematical paper that proposed a bold guess (a conjecture) and translated the entire thing into a computer language called Lean. Think of Lean as a super-strict referee that checks every single step of a math proof to ensure it is 100% logically sound, with no room for human error or "I think this works" moments. The paper doesn't solve the mystery of whether the prime-generating machine exists; instead, it builds a perfect, unbreakable digital model of the rules of the game.

The main finding of this work is that the entire theory behind the "Prime Machine" guess has been successfully coded into the computer. Every definition, every example, and every table of numbers from the original paper now lives inside this digital file. The author checked 89 different examples of these "natural functions" (the fancy name for the machines built from addition, multiplication, and powers). For each one, the computer calculated the results and confirmed that they all eventually fail to produce a prime number. For instance, one function worked perfectly for the first six numbers but broke on the seventh. The computer proved these failures with absolute certainty, using advanced digital certificates to verify huge numbers that would take a human years to check by hand.

However, the paper is very clear about what it hasn't done. It has not proven that the Prime Machine is impossible. It has not found the ultimate answer. The central guess—that no such machine exists—remains an open problem, a "named open problem" in the computer code, waiting for a human or an artificial intelligence to finally prove it. The paper essentially says, "Here is the exact rulebook, and here is the evidence that every machine we've tried so far fails, but the final verdict is still out."

The author also expanded the game slightly. They asked, "What if we add a few more tools, like factorials (multiplying a number by all the numbers below it) or Knuth arrows (a way to write huge powers)?" They built a new, larger class of machines with these extra tools and stated a new, even harder version of the guess: that even with these super-tools, you still can't build a machine that only makes primes. This new guess is also left open, unproven, but now it is written down in a way that a computer can check if someone eventually figures out the proof.

In short, this paper is a massive act of translation and verification. It takes a complex mathematical idea about the chaotic nature of prime numbers and locks it into a digital vault where every rule is checked by a machine. It confirms that for every specific example tested, the "Prime Machine" fails, but it leaves the ultimate question of whether such a machine is theoretically possible as a challenge for the future. The primes, it seems, are indeed "supernatural," resisting any simple formula we try to trap them with.

Technical Summary: The Set of Primes is Supernatural: A Lean Formalization of the Statement of the Conjecture

Problem Statement
The paper addresses the formalization of the "Supernatural Primes Conjecture" originally proposed in [3]. The conjecture posits that no non-constant function, constructed from the identity function and constants using finitely many pointwise additions, multiplications, and exponentiations, maps every positive integer to a prime number. The paper aims to translate this conjecture and its surrounding theoretical framework into a machine-checked formalization using Lean 4 and the Mathlib library. The goal is to establish a precise, kernel-checked target for the conjecture, allowing both human and automated reasoning systems to attempt a proof.

Methodology
The formalization is contained entirely within a single Lean 4 file, SPCL.lean (approximately 1200 lines), which depends solely on Mathlib. The methodology involves a direct, exhaustive translation of the source paper [3] into Lean, ensuring that every definition, example, remark, numbered result, and experimental table row has a machine-checked counterpart.

Key technical components include:

Elevation Structures: The paper axiomatizes the compatibilities of addition, multiplication, and exponentiation as an "elevation structure" (a 4-tuple $(E, +, \times, \wedge)$ ). This is formalized as a type class, and the category of such structures is constructed with identity and composition laws.
Natural Functions: Two equivalent encodings of "natural functions" are implemented:
1. Word Construction: Functions are generated by finite words over the alphabet $\{A_+, A_\times, A_\wedge\}$ applied to the set of identity and constant functions.
2. Inductive Closure: An inductive predicate IsNatural is defined with constructors for identity, constants, and the three operations.
  The equivalence between these two definitions is formally proved.
Conjecture Formulation: The conjecture is stated as a named proposition (Conjecture_2_1) of type Prop without a proof. It is explicitly defined as a hypothesis rather than an axiom or a sorry-filled theorem, ensuring the formalization introduces no new assumptions.
Experimental Verification: The paper formalizes 89 experimental results from [3, §4]. These are stated as theorems asserting the primality of specific function values up to a certain point and the compositeness of the first non-prime value.
- For smaller values, proofs rely on norm_num (computational evaluation).
- For large values (e.g., $2^{2^6} + 93$ ), the formalization uses Lucas primality certificates. These are verified via a custom lucasCert lemma that checks the conditions $a^{p-1} \equiv 1 \pmod p$ and $a^{(p-1)/q} \not\equiv 1 \pmod p$ for prime factors $q$ of $p-1$ , using Mathlib's reduce_mod_char tactic.

Key Contributions

Exhaustive Formalization: The paper provides a complete, "sorry-free" formalization of the entire paper [3]. Every definition, lemma, proposition, and table row is present in the Lean code.
Precise Conjecture Target: By stating the conjecture as a named, unproved Prop, the work creates a specific, verifiable goal for automated reasoning systems. The dependency structure is transparent; any proof of the conjecture would rely only on the formalized definitions and axioms of Lean/Mathlib.
Mathematical Extension: The formalization extends the theory of [3, Remark 3.4] by defining a broader class of functions, IsNaturalKnuthFactorialSub. This class includes:
- Knuth's up-arrow notation (where the arrow level is itself a function in the class).
- The factorial function.
- Truncated subtraction (under the condition $g(n) < f(n)$ ).
  The paper proves that the original class of natural functions embeds into this extended class.
Verification of Proved Cases: The formalization includes proofs for the cases where the conjecture is known to hold (e.g., non-constant polynomials, linear-exponential forms, and Fermat's function), utilizing standard number-theoretic results from Mathlib (e.g., polynomial divisibility, Fermat's Little Theorem).

Results

Formal Consistency: The SPCL.lean file compiles in approximately 30 seconds. It relies only on Lean's standard classical axioms (propositional extensionality, quotient soundness, choice) inherited from Mathlib.
Experimental Tables: All 89 rows of the experimental tables from [3] are formalized as theorems. The proofs for large primality claims are verified via kernel-checked Lucas certificates, eliminating the risk of transcription errors in factorization strings.
Theoretical Equivalences: The formalization proves the equivalence between the functional formulation of the conjecture and its set-theoretic reformulation (that the set of primes is "supernatural," meaning it contains no infinite natural subset).
Consequences: Conditional on the conjecture, the formalization proves that the set of composite Fermat numbers is infinite and that the set of non-prime values for any non-constant natural function is infinite.

Significance
The paper claims its primary significance lies in the rigor and completeness of the formalization. It transforms a "hard challenge for any kind of intelligence" (as described in [3]) into a precise, machine-verifiable target. By removing all ambiguity and ensuring every step is checked by the Lean kernel, the work allows automated reasoning systems to attempt a proof of the conjecture without the risk of human error in the underlying definitions. The paper does not claim to solve the conjecture but rather to provide the necessary infrastructure for such a solution to be validated. It also demonstrates the feasibility of formalizing complex, experimentally-driven number theory conjectures within the Mathlib ecosystem.

Technical Summary: The Set of Primes is Supernatural: A Lean Formalization of the Statement of the Conjecture

More like this