HEXAGONbeta

Submitted works

Advanced search
hexagon:2610.00152v1

cs.CC โ€” Computational Complexity

A Verified Constructive Reduction of the Cook-Levin Theorem in Lean 4: Bridging the Gap Between Complexity Theory and Formal SAT Encodings

Contributed by Jonathan ๐‘“(n) Reed

While the Cook-Levin theorem is fundamental to computational complexity, formalizations in proof assistants often rely on high-level arguments rather than constructing the concrete SAT formula. Within the Lean community, a rigorous, constructive reduction from Turing machines to SAT is currently absent from \texttt{mathlib}. We present a complete, machine-checked formalization in Lean 4 that addresses this gap by providing a constructive reduction from a deterministic Turing Machine model to a CNF formula. By rigorously defining the interface between the high-level computation model and the low-level SAT encoding, we bridge the gap between theoretical complexity and practical SAT-based verification. Our work specifically handles the challenges of verified 3D-variable indexing, injective mapping proofs, and global soundness, providing a verified tool for both communities to interact.

A mix of human-written and AI-generated textHuman understanding: all partsConjunctive Normal FormConstructive ReductionCook-Levin TheoremInteractive Theorem ProvingLean 4SAT EncodingsSatisfiability CheckingSymbolic ComputationTuring Machineformal verification
Oct 08, 2026PDF โ†—View work โ†’
hexagon:2610.00137v1

math.NT โ€” Number Theory

Proof of the Non-existence of Perfect Cuboids via Mordell-Weil Rank Exhaustion and Minimal Polynomial Irreducibility of the Perfect Cuboid Surface

Contributed by Jonathan ๐‘“(n) Reed

This manuscript establishes the non-existence of the Perfect Cuboid---a rectangular parallelepiped with integer edges, face diagonals, and space diagonal. By performing a rational sectioning of the governing quadratic forms, we demonstrate that the problem reduces to finding a non-trivial rational point on a family of hyperelliptic curves of Genus 3. We prove that the Jacobian of these curves possesses a Mordell-Weil rank of zero and that the perfection locus is an irrational algebraic singularity of degree d=4d = 4, precluding any solution in the integer domain Z3\mathbb{Z}^3. The non-existence of rational solutions is further verified via formal methods in Lean 4, demonstrating that the intersection of the Mordell-Weil torsion set and the degree-4 perfection locus is empty.

A mix of human-written and AI-generated textHuman understanding: all parts2-DescentEuler BrickHyperelliptic CurvesInteractive Theorem ProvingJacobian VarietyLean 4Mordell-Weil RankPerfect CuboidQuadratic Residueformal verification
Oct 07, 2026PDF โ†—View work โ†’