CS Paper Radar

A First Introduction to Isabelle/ML Metaprogramming: Automatic Estimation of Polynomial Degrees

Jonas Bayer, Anna Danilkin, Marco David, Annie Yao

cs.LO ·submitted 2026-10-06 13:49 UTC · v1

Abstract

This article offers an introduction to metaprogramming in Isabelle/HOL for beginners, based on a running example for working with multivariate polynomials. The example is motivated by our formalisation of universal Diophantine pairs. We describe the implementation of the poly_degree command, which computes upper bounds on the total degrees of multivariate polynomials and automatically proves their correctness. The complete metaprogram handles a variety of special cases but herein we present a simplified version for the sake of exposition. We describe our development process and design decisions; our goal is to offer a small and self-contained tutorial on Isabelle/ML, for mathematicians who want to get started with metaprogramming.

Closest papers

Nearest neighbours by meaning across the whole index.

Python Code Generation for Isabelle/HOL

cs.PL cs.LOcs.SE ·2026-11-17 ·Nikolaus Huber, Roly Perera, Dominic Orchard
theory similarity 0.69
Abstract · 20 pages, 19 figures, 2 tables. Software artefact: https://doi.org/10.5281/zenodo.24106993

The Isabelle theorem prover provides an environment for formalising mathematics and reasoning about programs. To make verified implementations practically usable, its code generator translates functions expressed in the executable fragment of its logic into conventional programming languages. Its targets have traditionally been functional languages (Standard ML, OCaml, Haskell, and Scala), recently joined by Go. Python, which is becoming the dominant language of scientific computing, data science, and education, has remained out of reach. In this work, we close this gap with a Python backend for Isabelle's code generator. This generator enables verified algorithms to be used in Python applications, or to serve as verified references against which established Python libraries can be differentially tested, without leaving the Python ecosystem. We validate the backend on regression suites covering large parts of the HOL library and by testing six verified data structures and algorithms against established Python libraries. The generated code is slower than hand-written libraries, but well suited as a verified reference.

0.24

IsaGraphLib: Formally Verified Efficient Graph Algorithms in Isabelle/HOL

cs.DS cs.MS ·2026-11-15 ·Mohammad Abdulaziz, Thomas Ammer, Adem Rimpapa, Peter Lammich
similarity 0.60
Abstract

We present a library of formally verified graph algorithms in Isabelle/HOL. The library covers the main problems of combinatorial optimisation on graphs: reachability, shortest paths, minimum spanning trees, matching, maximum flow, and minimum-cost flow. The algorithms in the library use most of the standard algorithm design techniques: graph search, greedy algorithms on matroids, dynamic programming, augmenting paths, blossom contraction, blocking flows, push-relabel, scaling, the primal-dual method, randomisation, and certificate checking. The library has adaptors between different types of graphs (directed, undirected, multigraphs), which allow results to be reused. Each algorithm is verified independently of its data structures, and the main algorithms are refined to efficient imperative implementations, from which we generate code in Standard ML, Scala, and Go. We developed parts of the library with large language models (LLMs), improved the quality of their proofs with a method based on statistics of our own proofs, and labelled which parts were developed by humans, by LLMs, or collaboratively. We perform a detailed experimental analysis of representative algorithms in our library, comparing it with state-of-the-art mainstream libraries, showing that our implementations are practical.

0.28

Sundance: A Simple SMT Solver for Program Verification

cs.LO ·2026-11-03 ·Amar Shah, Benjamin F. Jones, Can Cebeci, Jason Z. S. Hu, Lee A. Barnett +4 more
similarity 0.58
Abstract

We present Sundance, an SMT solver for program verification written in about 13,600 lines of Rust. Sundance combines the Cadical SAT solver with congruence closure, linear arithmetic, algebraic datatypes, and pattern-based quantifier instantiation. Sundance produces eDRAT proofs for every unsat answer. On 21,531 queries from Verus, Dafny, and F*, Sundance is comparable to existing solvers, with 26--38 times fewer lines of code than Z3 and cvc5. We further show that its components can be swapped for Z3's arithmetic solver, MiniSat, and the Semper e-graph. We have open sourced Sundance.

0.11

An algorithmic construction of Nullstellensatz certificates for graph automorphism groups

cs.SC cs.LO ·2026-10-20 ·Ivan Drecun
similarity 0.56
Abstract

Solvers for graph isomorphism and related problems are widely used in both theoretical and applied domains, but their complexity often requires users to trust their correctness without verification. We present a certifying algorithm for computing a generating set of the automorphism group of a given graph, meaning that it produces an independently verifiable certificate that the output list of automorphisms generates the entirety of the automorphism group. The problem of constructing a certificate is reduced to certifying that a system of multivariate polynomial equations is infeasible. An individualization-refinement algorithm produces a derivation within an algebraic proof system, representing a Nullstellensatz certificate of infeasibility. We provide an implementation of both the certifying algorithm and a certificate verifier, and demonstrate their viability on graphs with hundreds of vertices.

0.31

A Simple Algebraic Proof of the PCP Theorem

cs.CC ·2026-08-18 ·Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, Madhu Sudan, Sophus Valentin Willumsgaard
publishedtheory similarity 0.55
Abstract · Fixed an error in Lemma 3.3 and modified the tests accordingly

We give the simplest known algebraic proof of the PCP theorem, involving only ingredients like code concatenation, polynomial interpolation, and polynomial multiplication. Specifically, we prove that graph 3-coloring has a polynomial-sized proof that can be verified by a verifier tossing logarithmically many coins and querying a constant number of bits in the proof. In particular, our proof does not involve any PCP compositions; notably, it does not invoke the NP-completeness of any fixed problem, such as SAT or 3-coloring, in the construction of the verifier. The main innovation in our work is a clean, coding theoretic, way to encode univariate polynomials that allows us to implement ``low-degree testing'' using just a constant number of bits of queries. Insights from recent attempts to simplify the PCP proof by the authors (STOC 2026) and Goldreich (ECCC 2025) allow us to observe that low-degree was the key bottleneck in converting previous algebraic constructions of the PCP verifier into a constant query PCP. Thus, by overcoming this bottleneck, we get the full PCP verifier using elementary and self-contained steps. As concrete support for the claimed simplicity, we include the full pseudocode of the PCP verifier, assuming finite field arithmetic, and a full description of the completeness (aka ``honest'') prover, assuming multivariate polynomial arithmetic including interpolation and evaluation, that fit in about a page each.

0.32

Ramanujan Challenge Results: AI-Assisted Evaluation Pipeline for Multi-Format Proofs

cs.AI cs.CLcs.SCmath.NT ·2026-10-29 ·Alan Sorani, Ashvni Narayanan, Michael Shalyt, Tali Monderer, Rotem Kalisch +6 more
benchmark similarity 0.55
Abstract

As AI's mathematical capabilities rapidly improve, meaningful benchmarks are shifting from university-level problems and math olympiads to research-level mathematics. The Ramanujan Challenge is a benchmark comprised of research-level problems in number theory, including unpublished results and open conjectures. It presented concrete formulas for mathematical constants whose correctness can be checked numerically, while their proofs may require non-obvious mathematics. Here, we analyze the Challenge submissions, measuring the relative success of different AI models, Computer Algebra Systems (CAS), and formal tools. We find correct submissions that are conceptually distinct from the official solutions, and a proof of one of the published open conjectures. Evaluating the submissions exposed a second challenge: judging complex proofs reliably at scale. We introduce an AI-assisted evaluation pipeline for natural language proofs, CAS code, and Lean formalizations that assesses semantic and logical correctness. Compared with the conventional one-shot LLM judgment, our pipeline reduces false-positive verdicts on natural language proofs from 23% to 6% and improves judgment accuracy on supporting code from 46% to 58%. This approach provides a methodology for evaluating research-level mathematics at scale, with potential applications across mathematics and AI for science.

0.19

A Formalisation of a Special Case of the Union-Closed Conjecture in Isabelle/HOL

cs.LO ·2026-09-16 ·Angeliki Koutsoukou-Argyraki, Lawrence C. Paulson
similarity 0.55
Abstract · Submitted to J Automated Reasoning

A 2021 proof of a special case of the Union-Closed Conjecture, by Aaronson, Ellis and Leader, has been formalised in the proof assistant Isabelle/HOL. Our discussion involves sketching their proof and displaying snippets from the Isabelle version of the proof, illustrating the extent to which mathematical reasoning can be rendered clearly in a formal language.

0.25

Ideal Membership in Polynomial Calculus: Complexity and Reductions

cs.CC ·2026-09-23 ·Alex Bortolotti, Monaldo Mastrolilli
theory similarity 0.54
Abstract

The Ideal Membership Problem (IMP) asks whether a polynomial f belongs to an ideal <p_1, ..., p_m> of Q[x_1, ..., x_n]. Polynomial Calculus (PC) certifies membership by deriving f from the generators, and a degree-d derivation needs at most n^O(d) steps. We write PC-IMPd for the problem of producing a degree-bounded PC certificate, and call it solvable when one is guaranteed to exist and can be found in time n^O(d). Over Q, unlike over finite fields, a derivation may need exponentially many bits. We study PC-IMPd on instances arising from constraint satisfaction problems, and ask for which constraint languages L it is solvable. Our main contribution is a reduction framework for PC-IMPd, based on pp-definitions, pp-interpretations, and pp-encodings, that mirrors the algebraic approach to CSP complexity. Solvability is preserved by these constructions and, in the language of algebras, by passing to subalgebras, finite direct powers, and homomorphic images. We obtain new tractable classes over ternary and larger domains: every language closed under the median operation on a finite chain has solvable PC-IMPd, by reduction to the Boolean majority algebra, and in particular so does every language over {0, 1, 2} closed under a fixed-value majority. This also places IMPd(L) in P for such languages, advancing the classification of IMPd over ternary domains. In the process, we settle the last open case of the Boolean dichotomy for IMPd(L) and complete the Boolean classification of PC-IMPd(L) with an unconditional lower bound for an instance of PC-IMP1. A recent PC-to-SoS simulation reduces degree-automatability of Sum-of-Squares (the open problem of finding a degree-d SoS proof in time n^O(d) when one exists) to solvability of PC-IMPd. Each new tractable class therefore yields a family of constraint systems on which SoS proofs are degree-automatable.

0.24