Papers for

proof system developers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Hierarchy of arithmetical systems reveals role of negation principles

Arithmetical Characterizations of Two Intuitionistic Logical Principles

Abstract: This paper investigates the role of negation in arithmetic by analyzing subsystems based on subminimal logic. We introduce NA^PR, a system of subminimal arithmetic equipped with all primitive recursive functions, and answer the following four questions: (1) Can we develop reasonable arithmetic within NA^PR? (2) Can we characterize logical rules Absorption of Negation (An) and Ex Falso Quodlibet (ECQ) by arithmetical principles? (3) Are there strict differences in deductive power among NA^PR, MA^PR, and HA? (4) Do MA^PR and MA, and NA^PR and NA have a similar mutual interpretability relationship as HA? We show the following: First, Heyting Arithmetic (HA) is shown to be a conservative extension of NA^PR for positive formulas. Based on NA^PR, we prove that (ECQ) is equivalent to the definability of disjunction, and that (An) is equivalent to a variant of the least number principle. Furthermore, using the constant domain neighbourhood semantics, we show that the systems NA^PR, MA^PR (written as NA^PR+(An)) and HA (written as NA^PR+(An)+(ECQ)) form a strictly increasing hierarchy of strength. Finally, we demonstrate the essential role of primitive recursive functions in weak arithmetic using classical countermodels.

Thu 29 OctLogic in Computer Science
The gist
This paper studies how different ways of handling 'not' affect arithmetic logic systems. The authors introduce a basic arithmetic system with all primitive recursive functions and explore how adding two logical rules—one about negation and one about contradictions—changes what can be proven. They show that these systems build on each other, getting strictly stronger. Their work clarifies the connections between logic rules and arithmetic principles, and how certain functions are essential for weaker arithmetic.
Open → 2610.40829v1

Exponential complexity lower bound proved for bit pigeonhole principle proofs

An exponential lower bound for the bit pigeonhole principle in resolution over parities

Abstract: Resolution over parities, $\mathrm{Res}(\oplus)$, is the characteristic-two version of resolution over linear equations: clauses are disjunctions of affine equations over $\mathbb F_2$. Superpolynomial size lower bounds were previously known only for restricted refutations: tree-like, regular, or of bounded depth. We prove that every DAG-like $\mathrm{Res} (\oplus)$ refutation of the bit pigeonhole principle with $n+1$ pigeons and $n=2^\ell$ holes has more than $\exp(n/(32768\ell^2))=2^{Ω(n/\log^2 n)}$ clauses, for every $\ell\ge32$, with no restriction on regularity or depth. The proof translates an arbitrary refutation with $S$ clauses into a polynomial calculus refutation of degree $O(\log n)$ over $O(S+n^2)$ groups of extension variables in the style of Buss, Impagliazzo, Krajicek, Pudlak, Razborov, and Sgall. One substitution then removes all extension variables at once and leaves a nonzero low-degree polynomial derived from the pigeonhole axioms alone at degree at most $n/2$; a degree lower bound in the style of Razborov, proved through the homology of chessboard complexes, shows that no such derivation exists. The argument also yields a general sufficient condition for $\mathrm{Res}(\oplus)$ size lower bounds. The main theorem, this condition, and all their dependencies are formalized in Lean 4, and every statement links to its formal proof. The proof was developed with substantial AI assistance within an open research framework described in the final section.

Sat 19 SeptComputational ComplexityLogic in Computer Science
The gist
The authors showed that any logical proof method called resolution over parities needs an extremely large number of steps to prove a basic counting puzzle known as the bit pigeonhole principle. This means these proofs cannot be made efficient by restricting their structure. The finding uses advanced math and computer-assisted verification to confirm the result rigorously. Such limits help us understand why some logic puzzles are inherently hard for certain automated reasoning methods.
Open → 2609.23015v1