Sparse Elementary Certificates for Partition Congruences

Number theorists regularly prove statements like "the number of 5-colored overpartitions of $8n+7$ is always divisible by 128" with a computer algorithm that works over modular forms, a class of highly symmetric functions. The algorithm returns "true," but it does not give a proof a combinatorialist can read. Several recent papers state this plainly and ask for "completely elementary" proofs of results they could only settle by machine. We propose to compile these machine proofs into short algebraic certificates. Each certificate expresses the target congruence as an explicit combination of a small number of classical product identities, such as the Jacobi triple product. The certificate can be checked exactly by polynomial arithmetic in the Lean proof assistant, and it is chosen to be as sparse as possible.

The approach borrows from two other areas. From proof complexity it takes the Nullstellensatz view of a proof: an identity is proved by writing the difference of its two sides as a weighted sum of known identities, and the proof is judged by how many terms and how high a degree it needs. From computability theory it takes the requirement that checking a certificate must never involve open-ended search. In short, we treat the missing elementary proofs as the output of a sparse search over combinations of known identities, measure proof simplicity with numbers, and verify the results formally.

Core Claim

The standard machine proof is Radu's algorithm, implemented in Mathematica by Smoot. It maps a partition generating function onto a modular curve, runs a subroutine (minN) to pick a level parameter, and then reduces an infinite congruence to checking finitely many coefficients up to a Sturm bound. That is how Saikia sharpened $p_5(8n+7)$, $p_{11}(8n+7)$ and $p_{13}(8n+7)$ to divisibility by 128, 64 and 256, where earlier manual work reached only 32. It is also how Nath and Saikia proved the $7^a$ families for $K(n)$ and $L(n)$, and how Alanazi, Munagi and Saikia handled their Section 4 congruences for doubly regular overpartitions. Both of the latter papers explicitly ask for elementary proofs.

Our claim is that most of these results admit a certificate of the following form. Write each generating function as a polynomial in formal symbols $f_k$, where $f_k$ stands for the infinite product $\prod_{i\ge1}(1-q^{ki})$. Fix a finite dictionary of classical identities $L_j = R_j$: product identities, 2-, 3- and 5-dissection formulas, and the modular equations of degree $p$ in their classical product form. A congruence $\sum_n c(Qn+\beta)q^n \equiv 0 \pmod{p^\lambda}$ is certified by integer polynomials $G$ and $g_1,\dots,g_m$ in the symbols such that

$$ D_\beta - p^{\lambda} G = \sum_{j=1}^{m} g_j \,(L_j - R_j), $$

where $D_\beta$ is the progression's generating function expressed through the dictionary's dissection identities.

Everything here is a formal polynomial identity. Checking it is exact ring normalization, not coefficient comparison up to a truncation. Every dictionary entry has a textbook elementary proof, so the certificate is an elementary proof by construction.

For families indexed by $\alpha$, the same template certifies two things. The first is the base case. The second is a one-step recurrence showing how the operator "take every $p$-th coefficient" acts on a finite set of product basis functions. That leaves a finite integer-matrix check that $p$-adic divisibility grows with $\alpha$.

The certificate has three complexity measures, which play the role that "hypothesis complexity" plays in Finding Simple Proofs for First-Order Optimization:

  • $m$, the number of dictionary identities used;
  • the total number of monomials in the $g_j$;
  • the maximum degree of the $g_j$.

The claim is falsifiable in two ways. The search might find no certificate within a reasonable degree for the theorems that currently lack elementary proofs. Or the certificates it finds might be no smaller than a direct transcription of Radu's coefficient check.

Research Program

The first component is a solver. For a target congruence and a degree budget $d$, we set up the certificate equation as a linear system over the integers, with unknowns the coefficients of $G$ and the $g_j$. Solving it modulo $p^\lambda$ gives a dense feasible certificate. We then sparsify it.

The sparsification follows Thomsen et al., who turned dense dual certificates from semidefinite programs into three-hypothesis proofs. They found that plain $\ell_1$ penalties fail to track the optimal sparsity as the problem grows, while a normalized log-sum penalty succeeds. Their paper supplies the method; our setting differs in that the certificate lives in an integer polynomial ring rather than in real Lagrange multipliers. We therefore alternate a relaxed log-sum solve, which selects the active identities, with an exact integer re-solve restricted to that support. We then prune identities greedily for as long as the exact solve stays feasible.

When the dictionary is too weak, we add lemma discovery. We mine intermediate identities between pairs of products that recur across many certificates, prove each one once, and add it to the dictionary. This parallels Thomsen et al.'s recovery of potential functions.

The second component is formal verification. Each certificate is emitted as a Lean 4 file. The file imports the dictionary identities as proved lemmas; where a lemma is not yet in the library, we state it as an explicitly marked axiom and count it. The file then discharges the polynomial identity with a ring-normalization tactic.

This matters because Smoot's outputs are currently Mathematica scripts, with no connection to a proof checker. It also sidesteps the distortion noted in miniF2F, where proof length depends heavily on which proof assistant is used. Our complexity measures are defined on the algebraic certificate, so they do not depend on tactic style.

The third component uses computability theory as a constraint rather than a topic. Kalociński, San Mauro and Wrocławski study "punctual" presentations, meaning structures whose basic operations can be computed without unbounded search. They also show that whether such a presentation exists can hinge on the chosen signature. Two lessons carry over:

  • Checking must be bounded. Our certificates are checkable in time bounded by an explicit primitive recursive function of their size. The one piece of Radu's pipeline without such a bound is the minN level search.
  • Encoding matters. Encoding the same generating function as a polynomial in the symbols $f_k$ or as a coefficient sequence can change whether a short certificate exists at all.

The theoretical question we pursue is whether the degree $d$ needed for a certificate can be bounded explicitly in terms of the level and weight data Radu's method produces. A positive answer would make the whole route from input to certificate a bounded-search procedure.

We deliberately do not pursue degree spectra of congruence relations on $(\omega,<)$, as in Intrinsic Complexity of Recursive Functions on Natural Numbers with Standard Order. A congruence along an arithmetic progression defines a relation that is decidable once Radu's method applies, so its degree spectrum carries no information. We see that direction as a dead end.

Baselines

Radu–Smoot machine proof (naive reference). The reference point is Radu's algorithm as run in the cited papers. It already establishes every target congruence, so "doing nothing" means keeping those proofs. We record its proof size as the Sturm bound (the number of coefficients checked) together with the size of the modular-function relation it verifies. We reuse the same generating functions and moduli, for example Saikia's 128, 64 and 256.

A certificate beats this baseline if it reaches exactly the same modulus while being elementary (every dictionary lemma has a classical proof) and formally checked in Lean. For headline success we also require that it be smaller than the machine proof.

There is no reported result found on Lacuna for converting Radu certificates into elementary or formal proofs, so our first-run numbers establish the baseline for that task.

Agent-based proof optimization (strongest existing method). The strongest existing automated competitor is ImProver. It combines LLM agents that annotate each proof step with the current hypotheses and goals, a compiler-feedback repair loop, and retrieval over Mathlib. It reports a 30.54% average length reduction on Mathematics in Lean, rising to 55.29% on eligible proofs, with 100% compilation correctness. Plain GPT-4o prompting reaches only 6.25% on the same data.

We give ImProver-style agents the same targets, the same dictionary as retrievable Lean lemmas, and a matched token and compute budget. They may either produce an elementary Lean proof from scratch or shorten our dense certificate. Our method wins if it certifies more theorems at the correct modulus, or produces smaller certificates on the theorems both methods solve.

Ablations. Two ablations isolate the key ingredients.

  • $\ell_1$ ablation. We replace the log-sum sparsifier with plain $\ell_1$ at equal solver time. This tests whether the non-convex penalty matters in the integer setting as it did for Thomsen et al.
  • No-lemma-discovery ablation. We freeze the dictionary. This measures how much the mined lemmas contribute.

Human elementary proofs. Where published elementary proofs exist, as for Theorems 1–4 of Nath and Saikia, we transcribe them into the certificate format and compare sizes directly.

Why not just…?

Why not just keep using Radu's algorithm? For establishing truth, it suffices. But the authors who use it say it does not give the readable proof they want. Nath and Saikia and Alanazi et al. both list elementary proofs as open problems, and the minN step remains an unbounded search. Our first experiment reports, theorem by theorem, whether the elementary certificate is actually shorter than the machine check. If it is not, we will say so.

Why not just ask an LLM agent to write elementary Lean proofs? This is a real threat, and we run it as the main baseline under an equal budget. The evidence against it is indirect. miniF2F reports that GPT-f reaches 29.2% pass@8 on Olympiad problems in Lean. The congruences here require multi-page dissection algebra that manual experts themselves could not complete. We expect agents to be most useful for shortening our certificates, and the experiment measures that combination explicitly.

Why not just solve the linear system and stop, or use $\ell_1$? A dense feasible certificate is already elementary, so sparsity could be cosmetic. However, Thomsen et al. found that $\ell_1$ stops tracking optimal sparsity as proofs lengthen. Dense certificates with hundreds of identities are no more readable than Radu's output. The $\ell_1$ ablation decides whether the extra machinery earns its place in this domain.

Why not just formalize modular forms in Lean and verify Radu's output directly? That would produce trustworthy proofs, but not elementary ones, and it requires formalizing modular curve theory before a single congruence is checked. Our route needs only classical product identities. It therefore answers the question the number theorists actually posed.

Proposed Experiments

The benchmark consists of the congruences stated in the file.

We report five metrics:

  • the fraction of theorems certified at the published modulus;
  • the three complexity measures ($m$, monomial count, degree);
  • Lean kernel checking time;
  • the size ratio against the Radu–Smoot check;
  • how the minimal certificate degree grows with the modulus exponent $\lambda$ and with the family parameter $\alpha$.

Three checks are decisive:

  • Controls. On the positive controls, the solver should recover certificates no larger than the transcribed human proofs.
  • Open cases. On at least some of Nath–Saikia Theorems 6–7 and Alanazi et al. Section 4, it should produce a Lean-verified elementary certificate. That would resolve open problems the authors posed.
  • Degree growth. Across Saikia's four moduli, the certificate degree should stay bounded or grow predictably. This is the empirical test of whether an explicit degree bound, and hence a bounded-search procedure, is plausible.

If the degree grows without an apparent pattern as $\lambda$ increases from 32 to 256, that is evidence that elementary methods face an intrinsic size cost at high prime powers. That negative finding would also be worth publishing.