Matching works

20 works

cs.LO — Logic in Computer Science

A formal proof in Lean of the finiteness of planar five-body central configurations for all positive masses

Contributed by Tejasvi Singh Tomar

Smale's sixth problem asks whether, for every choice of positive masses, there are finitely many central configurations up to similarity. For five bodies in the plane, Albouy and Kaloshin proved finiteness outside a set of masses of codimension two. In a companion paper the author proved finiteness for every choice of five positive masses by their method, adding steps that cannot be checked by hand: exact computer algebra, rational certificates and a branch and bound. We formalize this theorem in Lean 4 with Mathlib without assuming the results of Albouy and Kaloshin that the informal proof uses. Instead we prove what the proof needs of their rules on limit diagrams, of their classification of these diagrams and of their mass conditions. We do so at places of complex algebraic curves, taken as valuations of the function field rather than points of a projective model. Almost every computation becomes data for a checker that we write in Lean, prove sound with respect to Mathlib's real and complex numbers, and run in the kernel (proof by reflection). The main theorem depends on about 680,000680{,}000 theorems proved in this way, and Mathlib's tactics prove the few other computations. The proof uses only Lean's three standard axioms, and two independent Lean kernels, nanoda and lean4lean, accept it.

Author comments: Published on Zenodo: https://doi.org/10.5281/zenodo.23723139

A mix of human-written and AI-generated textHuman understanding: all parts
Nov 12, 202619 pages
PDFView work

cs.LO — Logic in Computer Science

Formal Verification of a Computer-Assisted Proof in Celestial Mechanics

Contributed by Tejasvi Singh Tomar

Albouy, Fu and Sun conjectured in 2008 that four positive masses admit, for each cyclic order of the bodies, exactly one convex central configuration up to similarity; the question is Problem 10 of a 2012 list of open problems on the nn-body problem. We recently proved the conjecture by reducing it to an inequality for a trace at the real zeros of an equation in four variables; a branch and bound that starts from a grid of 136,448 boxes establishes the inequality. In this paper we describe a formalization of the whole proof in Lean 4 and Mathlib in which Lean's kernel checks the computation, using decide +kernel, so that no compiler has to be trusted. Our checker stores an interval as two natural numbers in a biased fixed-point format. The kernel can then hand all the arithmetic to GMP. Functions are enclosed over boxes by first-order slopes. An unverified search records the decisions for each box in one natural number, and the checker replays them. We write each formula once over a type class; evaluating it at a type that pairs a real number with an interval then proves the enclosure correct. Checking the 3418 certificate theorems takes 7.6 hours of processor time, and the independent type checker nanoda accepts the proof. A version rebuilt on one eighth of the boxes passed three type checkers in 2.9 hours on a public registry of formal proofs.

Author comments: Published on Zenodo: https://doi.org/10.5281/zenodo.23485952

A mix of human-written and AI-generated textHuman understanding: all parts
Nov 12, 202619 pages
PDFView work

math.RA — Rings and Algebras

Local optimality of rank-47 schemes for 4×4 matrix multiplication over F2

Contributed by Tejasvi Singh Tomar

The tensor ⟨4,4,4⟩\langle 4,4,4\rangle of 4×44\times4 matrix multiplication has rank at most 47 over F2\mathbb{F}_2, and as it is not known whether 47 is optimal, we ask how far the known decompositions of rank 47 are from one of rank 46. A decomposition is locally optimal to depth DD if no DD or fewer of its rank-one terms can be replaced by fewer rank-one terms. We prove that five pairwise inequivalent decompositions of rank 47 over F2\mathbb{F}_2 are locally optimal to depth 18, as is every decomposition equivalent to one of them, so a decomposition of rank 46 over F2\mathbb{F}_2 shares at most 28 terms with any decomposition in these five classes. The five classes include the scheme of Fawzi et al. and every public decomposition of rank 47 over F2\mathbb{F}_2 known to us; one of them, found in our flip-graph searches, is new. The proof rests on a peeling lemma and, for four sets of terms that resist the other bounds, on a refinement of the substitution method, which we call substitution over subspaces with lifting. Local optimality to depth 18 is also proved in Lean 4.

Author comments: Published on Zenodo: https://doi.org/10.5281/zenodo.23721965

A mix of human-written and AI-generated textHuman understanding: all parts
Nov 12, 202625 pages
PDFView work

cs.LO — Logic in Computer Science

Re-proving native_decide facts in Lean's kernel: a study of 16 public packages and a converter

Contributed by Tejasvi Singh Tomar

Lean's native_decide proves a decidable proposition by running compiled code and records the result as an axiom. Mathlib forbids such axioms, and lake check and Comparator in Lean 4.35 reject them, as do the independent proof checkers. NativeTrust re-proves the recorded facts in Lean's kernel, with only the standard axioms and without editing the projects that contain them. Where a definition blocks kernel evaluation and NativeTrust has a version proved equal to it (for example, a fuel-indexed form of well-founded recursion), the converter evaluates a copy that uses that version. It then proves the copy equal to the original, usually by congruence. With its default settings it converts 98.2% of 52,821 native facts in 16 public packages. The three largest packages hold 94% of these facts; outside them it converts 68.5%. Nearly every converted fact needed nothing beyond plain kernel evaluation. Two tools remove the native axioms that the kernel can prove within a budget: a single import that makes each call of the tactic try the kernel first, and a source rewriter.

Author comments: Published on Zenodo: https://doi.org/10.5281/zenodo.23818391

A mix of human-written and AI-generated textHuman understanding: all parts
Nov 12, 202627 pages
PDFView work

math.HO — History and Overview

The Rising-Sea Theses: Twelve Theses on Mathematics and Machine Reasoning

Contributed by Vincent Liu

The Grothendieckian Programme is a set of seven works on machine reasoning about mathematics (34 volumes, 26,021 pages), released openly in October 2026 as first drafts that have not been peer-reviewed. This paper draws from them twelve theses on how mathematics and machine reasoning should be combined. Each thesis is stated in one sentence, argued, tied to the passages of the seven works on which it rests, related to existing work, and paired with an observation that would refute it. The theses concern the unit of mathematical knowledge for a reasoning system, the place of epistemic status, the latent space of mathematical reasoning, attention, failure, authority, and the method of discovery. The paper adds no mathematical result to the seven works; none of them claims a proof of the Riemann Hypothesis, the Birch and Swinnerton-Dyer conjecture, the Hodge conjecture, the abc conjecture or the Langlands correspondence.

Author comments: 26 pages, 5 figures. Version 1.0 of 28 October 2026; the same text is deposited at Zenodo, DOI 10.5281/zenodo.23734424 (all versions: 10.5281/zenodo.23734423). This copy was typeset with pdfLaTeX for Hexagon: its text is identical to version 1.0 at Zenodo, whose sealed PDF was typeset with LuaLaTeX, except that a broken cross-reference on page 3 ("igref{works}") is corrected to "Figure 1"; a few line and page breaks differ. The twelve theses are also set out at https://github.com/AlienMuse/grothendieckian-problems/blob/main/THESES.md; the seven works on which they rest, each with its DOI, are listed at https://github.com/AlienMuse/grothendieckian-programme. Corrections recorded since version 1.0 to the seven works and to the papers: https://github.com/AlienMuse/grothendieckian-problems/blob/main/ERRATA.md. Companion papers: The Grothendieckian Programme: An Overview (DOI 10.5281/zenodo.23734421) and The 57 Grothendieckian Problems (DOI 10.5281/zenodo.23734426).

A mix of human-written and AI-generated textHuman understanding: all partsGrothendieckian Programmedescentepistemic statusformal verificationmachine reasoningrecursive mathematical discovery
Nov 10, 202626 pages
PDFView work

math.HO — History and Overview

The Grothendieckian Programme: An Overview — Seven Open Works on Mathematics and Machine Reasoning

Contributed by Vincent Liu

The Grothendieckian Programme is a series of seven works on machine reasoning about mathematics (34 volumes, 26,021 pages), released openly on Zenodo in October 2026 with an overview volume. Two of the works specify a reasoning architecture — a core that holds mathematical worlds as typed, versioned and verifiable objects, and a kernel that reasons inside such worlds by sites, sheaves and descent. Five apply one method, recursive mathematical discovery, to the Riemann Hypothesis, the conjecture of Birch and Swinnerton-Dyer, the Hodge conjecture, the abc conjecture and the Langlands programme, and record what it proves, what it reduces to stated hypotheses and what it leaves open. This paper describes the architecture, the five research subjects, the method, the published corpus and the open process by which the works are to be reviewed and continued. None of the works claims a proof of any of these conjectures; they are first drafts and have not been peer-reviewed.

Author comments: 10 pages, 3 figures. Version 1.0 of 28 October 2026; the same text is deposited at Zenodo, DOI 10.5281/zenodo.23734422 (all versions: 10.5281/zenodo.23734421). This copy was typeset with pdfLaTeX for Hexagon: its text, and its line and page breaks, are the same as in version 1.0 at Zenodo, whose sealed PDF was typeset with LuaLaTeX. The seven works it describes, each with its DOI, are listed at https://github.com/AlienMuse/grothendieckian-programme. Corrections recorded since version 1.0 to the seven works and to the papers: https://github.com/AlienMuse/grothendieckian-problems/blob/main/ERRATA.md. Companion papers: The Rising-Sea Theses (DOI 10.5281/zenodo.23734423) and The 57 Grothendieckian Problems (DOI 10.5281/zenodo.23734426).

A mix of human-written and AI-generated textHuman understanding: all partsGrothendieckian Programmedescentmachine reasoningmathematical worldsopen sciencerecursive mathematical discovery
Nov 10, 202610 pages
PDFView work

math.HO — History and Overview

The 57 Grothendieckian Problems: Open Problems for Mathematics and Machine Reasoning from the Grothendieckian Programme

Contributed by Vincent Liu

We state fifty-seven open problems drawn from the seven works of the Grothendieckian Programme (34 volumes, 26,021 pages, released openly in October 2026 as first drafts that have not been peer-reviewed). Thirty-five come from the two works on the architecture of a reasoning system and twenty-two from the five works that each take a named conjecture or programme as research subject; no problem is one of those conjectures. Each problem is stated in the words of its source, located by work, chapter and page, given the status the source assigns it, and paired with a criterion that decides when it is solved, a note on existing work and the date of a literature check. The problems are of three kinds: twenty-five mathematical problems, nineteen machine problems with success criteria fixed in advance, and thirteen formalization problems for Lean 4 and Mathlib. Every quotation from the sources has been checked against the published PDFs, and each problem has been checked against the literature as of 28 October 2026; a machine-readable version accompanies the paper.

Author comments: 54 pages, 5 figures. Version 1.0 of 28 October 2026; the same text is deposited at Zenodo, DOI 10.5281/zenodo.23734427 (all versions: 10.5281/zenodo.23734426). This copy was typeset with pdfLaTeX for Hexagon: its text is identical to version 1.0 at Zenodo, whose sealed PDF was typeset with LuaLaTeX, and a few line and page breaks differ. Each problem has a public issue at https://github.com/AlienMuse/grothendieckian-problems, which also holds the machine-readable data, the literature-check records and the Lean statement of Problem 49. Corrections recorded since version 1.0, including literature missed by the check for Problem 18: https://github.com/AlienMuse/grothendieckian-problems/blob/main/ERRATA.md. Companion papers: The Grothendieckian Programme: An Overview (DOI 10.5281/zenodo.23734421) and The Rising-Sea Theses (DOI 10.5281/zenodo.23734423).

A mix of human-written and AI-generated textHuman understanding: all partsGrothendieckian ProgrammeLeandescentformal verificationmachine reasoningopen problems
Nov 10, 202654 pages
PDFView work

cs.LO — Logic in Computer Science

Formalizing the interpolation lemma of the openai/math Landau–Siegel paper and substituting it into a Comparator-accepted proof

Contributed by Joseph Reilly

OpenAI’s openai/math release includes a Lean formalization of “Uniform exclusion of Landau–Siegel zeros” (OpenAI, October 1, 2026). Its Comparator challenge has two checked theorems, whose statements we prove equivalent in Lean. OpenAI proves them by two routes, neither through the paper’s proof of Lemma 3. The catalogued main result, exists_absolute_real_zero_gap, gets its spanning step from a local Bézout argument and does not use OpenAI’s Corollary 4 theorem. The second theorem, dirichletRealZeroBound_proof, proves Corollary 4 by a multiplicity estimate. We formalized the paper’s proofs of Lemma 3 and Corollary 4 in Lean. By reading, the Lean statements match the paper’s, and the declarations use only the axioms propext, Classical.choice and Quot.sound. A +2/-1 substitution puts the paper’s Corollary 4 into dirichletRealZeroBound_proof. Comparator accepts the result with both kernels at openai/math fd4aeeb under a deny list of all 45 socket address families, and that theorem’s closure no longer contains the three named OpenAI lemmas. Our replay of the corpus agrees with an independent replay on all 402 configurations where both have a verdict.

Primarily AI-generated textHuman understanding: some parts
Nov 10, 202620 pages
PDFView work

cs.LO — Logic in Computer Science

Proof-Carrying Modernization: LLM Translations of COBOL Batch Programs, Each Proved Against the Original in Lean

Contributed by Tejasvi Singh Tomar

Large language models translate legacy code quickly, but a translation can differ from the original on inputs that no test exercises. We show that LLM translations of whole, unmodified COBOL programs into Rust and Java can be proved in Lean 4 to behave like our semantics of the originals on every admissible input: a bounded number of well-formed records, among other premises. The COBOL semantics is executable; it computes record layouts, decimal arithmetic and file handling from our front end’s output for the unmodified source. For the eight standalone batch programs of AWS CardDemo covered by that front end, all 16 translations are proved, as equivalences for Rust and as refinements with partial correctness for Java. The statements are generated from the programs except for a few small parts, LLM agents write the proofs, and Lean’s kernel checks them. Before any proof, 35% of the first running translations differed from our semantics of the original on a generated input, and no proof found a difference that this testing had missed.

A mix of human-written and AI-generated textHuman understanding: all parts
Nov 06, 202623 pages
PDFView work

math.CO — Combinatorics

Kernel Dimension of the Z/2 Connection Laplacian on a Finite Simple Graph (A Formalisation in Lean 4 / Mathlib v4.11.0)

Contributed by Jesus Vilela Jato

We present a Lean 4/Mathlib v4.11.0 formalization of the kernel-dimension theory of the Z/2\mathbb{Z}/2 connection Laplacian on finite simple graphs equipped with designated wrap edges. Each edge carries either the identity or the coordinate-swap matrix. A Hadamard–Kronecker change of basis decomposes the resulting rank-two connection Laplacian into the ordinary and signed graph Laplacians. An analogous splitting holds for the scalar Laplacian of the associated two-sheeted cover. A connected component is balanced precisely when its covering preimage has two connected components, equivalently when its sign holonomy is trivial along every closed walk. Consequently, the nullity of the signed Laplacian equals the number of balanced connected components, while the nullity of the full connection Laplacian equals the number of connected components plus the number of balanced components. For the flat connection, the nullity is twice the number of connected components. We also formalize exact characteristic polynomials and eigenvalue multisets, including multiplicities, for explicit ordinary and one-wrap signed cycle matrices for n≥3n \geq 3. Transfer to general connection-graph encodings remains conditional on specified matrix-reindexing identities. The contribution is a machine-checked formalization, exposition, and documented verification of results rooted in classical signed-graph spectral theory, rather than a claim of priority for those identities. The accompanying repository preserves proof artifacts, computational cross-checks, historical verification evidence, and documented corrections.

Primarily AI-generated textHuman understanding: some partsAI-assisted mathematicsLean 4connection Laplacianformal verificationgraph coverssigned graphsspectral graph theory
Nov 04, 202618 pages
PDFView work

math.CO — Combinatorics

The ten minimum universal sets of MacMahon cubes

Contributed by Jason Davies

A collection of six-coloured MacMahon cubes is universal if eight of its cubes can be selected to build a 2×2×22\times2\times2 model of any target variety, with matching exterior colours and no internal matching requirement. We prove that exactly ten labelled collections attain the known minimum size of twelve, even when repeated varieties are allowed, resolving the conjectures of Johnson and Roldán. Usable-cube inequalities force a symmetric multiplicity matrix with row and column sums two; corner coverage then forces two disjoint triangles in Conway's tableau. The written proof is elementary and requires no exhaustive search. The classification and its discrete geometric interpretation are formalised in Lean 4. Exhaustive computation provides a separate check and additional target-count distributions.

Primarily AI-generated textHuman understanding: some partsConway's tableauEight Blocks to MadnessLean 4MacMahon cubesuniversal sets
Nov 02, 20267 pages
PDFView work

math.RA — Rings and Algebras

The rank of 3×3 matrix multiplication over F2 is 23

Contributed by Tejasvi Singh Tomar

The rank of the tensor of 3×33\times 3 matrix multiplication over the field with two elements is at most 2323 by Laderman's algorithm, and Rudich and Rousseau recently proved that it is at least 2222. We prove that it equals 2323. Hence Laderman's algorithm uses the fewest multiplications among all bilinear algorithms over F2\mathbb{F}_2 and among all bilinear algorithms with integer coefficients. The proof uses the substitution method in the form developed by D'Ambrosio, Wang and Yang et al., which bounds the number of first factors of a decomposition that lie in a given subspace of the space of first factors. We sharpen these bounds for 111111 of Wang's 496496 classes of subspaces, constrain the ranks of the first factors through a 27×2727\times 27 flattening of the tensor, and list, up to symmetry, all sets of 2222 first factors that satisfy these constraints. An exact completion search shows that none of them is the set of first factors of a decomposition. The computation emits certificates, which are checked in the Lean 4 proof assistant. In one formal proof the largest checks are evaluated as compiled code, and in a second one the kernel evaluates every check, so that its final theorem depends only on the three standard axioms of Lean. The Lean proofs build on the formalization of Rudich and Rousseau and import their table of bounds and their reduction for block algorithms.

A mix of human-written and AI-generated textHuman understanding: all parts
Oct 26, 202618 pages
PDFView work

math.NT — Number Theory

The Number of Terms in Greedy Fibonacci--Lucas Representations

Contributed by Deep Bhattacharjee, Ushashi Bhattacharya

We prove Kimberling's conjecture on greedy representations by Fibonacci and Lucas numbers: the ratio of the number of Zeckendorf summands of 1,…,n1,\dots,n to the number of terms of their greedy representations tends to a limit in (1.2,1.4)(1.2,1.4), and the limit is (5−5)/2(5-\sqrt5)/2. We also prove the conjectures of Greathouse and Kurkov on the number of terms of the greedy representation.

A mix of human-written and AI-generated textHuman understanding: some partsFibonacci numbersLucas numbersZeckendorf representationformal verificationgreedy algorithmsummatory function
Oct 22, 20269 pages
PDFView work

math.CO — Combinatorics

The minimum number of distinct abelian squares in a binary circular word

Contributed by Deep Bhattacharjee

We prove that every binary circular word of length nn contains at least $\fl{(n-1)/2}$ distinct abelian squares, and we determine all words attaining this bound. This settles a conjecture of Simpson: its odd case holds, and in its even case the list of extremal words misses (ab)n/2(ab)^{n/2} for n≡2(mod4)n\equiv 2\pmod 4, n≥6n\ge 6. We then review the other problems of the survey: we conjecture, and verify to length 2727, that for odd nn the least number of non-equivalent abelian squares in a circular word is also (n−1)/2(n-1)/2, and we show that the least number of occurrences of abelian squares in a binary word of length nn is asymptotically proportional to nn or grows faster, and is below n3/2n^{3/2}.

A mix of human-written and AI-generated textHuman understanding: some partsParikh vectorabelian squarecircular wordcombinatorics on words
Oct 22, 202614 pages
PDFView work

math.CO — Combinatorics

Partitioning {1,…,n}\{1,\dots,n\} into parts of size at most three whose sums are powers of three

Contributed by Deep Bhattacharjee, Ushashi Bhattacharya

We prove unconditionally the conjecture of Gurvich and Naumova that for every n≥1n\ge1 the set {1,…,n}\{1,\dots,n\} can be partitioned into parts of at most three elements whose sums are powers of 33. The partition is given by an explicit recursion.

A mix of human-written and AI-generated textHuman understanding: some partsformal verificationpowers of threeset partitionzero-sum triples
Oct 20, 202611 pages
PDFView work

math.CO — Combinatorics

A graph with three card types and five vertex orbits

Contributed by Deep Bhattacharjee, Ushashi Bhattacharya

We prove that the answer to part~(b) of Problem~20.71 of the Kourovka Notebook is yes: there is a connected graph on 6363 vertices with exactly three isomorphism types of vertex-deleted subgraphs whose automorphism group has five orbits on the vertices. The graph is a Cayley graph of a Suzuki 22-group of order 6464 with one vertex removed.

A mix of human-written and AI-generated textHuman understanding: some partsCayley graphSuzuki 2-groupdivisible design graphpseudosimilar verticesvertex-deleted subgraph
Oct 17, 202611 pages
PDFView work

math.CO — Combinatorics

Every odd antihole is strongly chromatic-choosable

Contributed by Deep Bhattacharjee, Ushashi Bhattacharya

A hole in a graph is an induced cycle of length at least four, and an antihole is the complement of a hole. Odd holes and odd antiholes are the graphs that, by the strong perfect graph theorem, force the chromatic number above the clique number. Fiujlaali and McDonald studied the odd antiholes inside kk-critical graphs of maximum degree Δ\Delta, proved that such an antihole has at most 2(Δ−k)+72(\Delta-k)+7 vertices, and conjectured that this bound is attained only when the graph is the antihole itself, provided the graph has no odd hole. They reduced this to a statement about list colouring: for every ℓ≥3\ell\ge3, the odd antihole on 2ℓ−12\ell-1 vertices has chromatic number ℓ\ell, and the only assignments of lists of ℓ−1\ell-1 colours from which it cannot be coloured are those in which all lists are equal. This is their Conjecture~9, and they proved it when all the lists lie in a common set of ℓ\ell colours. We prove it for every ℓ\ell with no restriction on the lists, and we deduce their Conjecture~3 for all kk and Δ\Delta. The proof works with the complements of disjoint unions of paths with an odd number of vertices. The vertices in even positions of the paths form a clique in the complement, so equal lists of one colour fewer than the number of these vertices cannot be completed; we show by induction, using Hall's theorem and the theorem of Erd\H{o}s, Rubin and Taylor on complete multipartite graphs with parts of size at most two, that this is the only obstruction, and a separate lemma on minimal tight sets settles the extremal case of a single path. The cycle is then closed by carrying a colour shared by two consecutive vertices around the odd cycle in steps of two. The theorem also gives an infinite family of strongly chromatic-choosable graphs that are not strongly critical in the sense of Stiebitz, Tuza and Voigt. Every statement is proved by hand.

A mix of human-written and AI-generated textHuman understanding: some partschromatic-choosabilitycolouringcritical graphodd antiholeodd hole
Oct 17, 202611 pages
PDFView work

cs.LO — Logic in Computer Science

A Machine-Checked Kernel for Federated Automated Adjudication: Credibility Lattice Completion, Certificate Lifecycle Invariants, Certified Numerical Anchors, and a Parameterized Rice Template

Contributed by Chepin Zhang

We present a formally specified and machine-checked kernel for a federated automated adjudication system, in which independent computational lines judge mathematical and operational claims and deposit their verdicts, evidence, and certificates in a shared ledger. The kernel comprises five components. (i) A three-rung, three-track credibility lattice obtained as a completion of a legacy five-element poset: the completion is justified by an exhaustive enumeration over all 11^{3}=1331 ordered triples and is fully re-formalized in Lean 4, where the equational lattice laws, the order axioms, and the extremality properties of join and meet are all proved by the decide procedure over the finite carrier. (ii) A five-state certificate lifecycle machine with nine legal transitions and machine-checked invariants, likewise re-formalized in Lean 4; the formalization caught a specification flaw in one invariant (the originally stated grant-gating condition is false), and we report the corrected, machine-proved form. (iii) Certified numerical anchors: uniqueness of the gauged fixed point of circulant entropic-optimal-transport (Sinkhorn) systems, established by a Krawczyk interval operator with outward rounding across a six-instance family (k in {6,10 }, varepsilon in {1,1/2,1/5 }, later extended to ten instances), together with a second anchor family of five auction-algorithm assignment instances certified by interval dual brackets. We state plainly that the certification of these numerical anchors is carried by the Python interval-arithmetic layer; the attempted port to the Lean 4 interval library leancert is blocked by structural capability boundaries of that library (absence of the logarithm from its supported expression grammar and infeasibility of its determinant computation at the required dimensions), and the Lean files are formal statements, not machine-verified certificates. (iv) A parameterized Lean 4 template for Rice-type undecidability, consisting of a bridge theorem, an extensionality lemma, an instantiation generator, and discharged instances of increasing difficulty. (v) A minimal trusted computing base result: the soundness of an interval certificate checker (accept implies correctness), itself machine-proved in Lean 4. All Lean artifacts were verified on cloud infrastructure (Axiom Axle, environment lean-4.28.0) under the strict verify_proof channel, with axiom audits restricted to propext, Classical.choice, and Quot.sound, and no sorryAx. Empirical fuzzing over three certificate families observed zero false accepts; we report rule-of-three 95% upper bounds on the false-accept rate and explicitly do not claim a guarantee.

Primarily AI-generated textHuman understanding: some partsLean 4Rice theoremfederated adjudicationformal verificationinterval arithmeticmachine-checked certificates
Oct 11, 202616 pages
PDFView work

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, 202616 pages
PDFView work

math.LO — Logic

Five equations for first-order logic, modulo the structure of existential graphs

Contributed by Anthony Hart

Peirce’s existential graphs draw a first-order formula so that the order and grouping of conjuncts, the names and order of bound variables, the position of a quantifier relative to conjuncts that do not mention its variable, and how a network of equalities is written cannot be seen. We take these structural laws for granted. On top of them, five two-way laws are complete for ordinary first-order logic with equality over nonempty domains. That is, any two equivalent formulas are connected by applying the laws inside them, in either direction. The laws are double negation, deiteration X ∧ ¬(X ∧Y ) ⇔ X ∧ ¬Y , annihilation ⊥ ∧ X ⇔ ⊥, substitution of equals, and existential introduction X(a) ∧ ∃u.X(u) ⇔ X(a), and none of them follows from the other four. The first three were already known to be complete for the propositional part. We prove first-order completeness by reduction to Tarski’s representation theorem for locally finite cylindric algebras. A size-ordered search over first-order laws, run up to size 5, kept four of the five; deiteration has size 7 and was added by hand. We also show that a published basis for Spencer-Brown’s boundary algebra is incomplete.

Primarily AI-generated textHuman understanding: all partscylindric algebraexistential graphsfirst-order logic
Sep 29, 202614 pages
PDFView work

Advanced search

Text
Human understanding
Linked formalizations