Rózsa: Certified Equational Reasoning
Georgios Kissas
cs.LO
Oct 19, 2026 · v1
TL;DR
Python solver for magma law implications emits Lean certificates (proofs or countermodels) checked by the SAIR challenge's Lean judge.
Abstract
When does one equation imply another? Stage 2 of the SAIR Mathematics Distillation Challenge required teams to submit solvers to answer this question for sets equipped with a binary operation. For these sets, associativity, commutativity, or any other algebraic property was not assumed. Each answer required a proof or counterexample that could be verified by Lean. Programs also had to respect fixed resource limits. We present Rózsa, a Python solver that searches for both kinds of evidence. It begins with simple tests and considers more extensive searches when those fail. To find a proof, it applies a given equation and derives any further equations as needed, keeping a record of each step. To find a counterexample, it searches for operations on finite sets. It also tests one fixed infinite model. The given equation must hold for every assignment, while the target equation must fail for at least one. In either case, Rózsa turns the evidence into a Lean certificate. The submitted solver solved 199/200 problems (99.5%) in the official main evaluation getting the 6th overall position. Additional tests show that the solver can prove many implications linked by long chains of known results, but has limited success with infinite counterexamples. We explain the search methods, how they fit together, and what the unsolved cases reveal about their limits.
Problem
Stage 2 of the SAIR Mathematics Distillation Challenge asked solvers to decide whether one magma equation implies another. Each answer had to come with a Lean-verified certificate, either a proof or a counterexample, and solvers ran under fixed time and size limits.
Approach
Rózsa runs a fixed portfolio of bounded searches that alternates proof search and countermodel search. Proofs come from direct substitution, collapse detection, rewriting, and recording completion, which keeps a derivation graph of equality steps. Countermodels come from structured formula families, exhaustive small operation tables, constraint repair, and one fixed infinite model. The evidence is checked locally in Python, then translated into Lean code (hypothesis instances, congrArg, transitivity) and submitted to the judge.
Results
The submitted solver solved 199/200 problems in the official main evaluation, placing tied sixth. It solved 197/200 long-chain true implications but only 17.9% of finite/general boundary cases, which shows its limits with infinite counterexamples.
| Suite | Cases | Accepted | Solved rate | Unsolved |
|---|
| Public qualification | 1,669 | 1,669 | 100.00% | 0 |
| Previous-stage evaluation | 800 | 800 | 100.00% | 0 |
| Released Stage 2 main | 200 | 199 | 99.50% | 1 |
| Long-chain true | 200 | 197 | 98.50% | 3 |
| Finite/general boundary | 821 | 147 | 17.90% | 674 |
Solver results by evaluation suite