Agentic Neurosymbolic Collaboration for Mathematical Discovery: A Case Study in Combinatorial Design
Hai Xia, Carla P. Gomes, Bart Selman, Stefan Szeider
cs.AI
Mar 9, 2026 · v1
TL;DR
Formally verifies a tight lower bound on Latin-square imbalance discovered via neurosymbolic collaboration in Lean 4.
Abstract
We study mathematical discovery through the lens of neurosymbolic reasoning, where an AI agent powered by a large language model (LLM), coupled with symbolic computation tools, and human strategic direction, jointly produced a new result in combinatorial design theory. The main result of this human-AI collaboration is a tight lower bound on the imbalance of Latin squares for the notoriously difficult case $n \equiv 1 \pmod{3}$. We reconstruct the discovery process from detailed interaction logs spanning multiple sessions over several days and identify the distinct cognitive contributions of each component. The AI agent proved effective at uncovering hidden structure and generating hypotheses. The symbolic component consists of computer algebra, constraint solvers, and simulated annealing, which provides rigorous verification and exhaustive enumeration. Human steering supplied the critical research pivot that transformed a dead end into a productive inquiry. Our analysis reveals that multi-model deliberation among frontier LLMs proved reliable for criticism and error detection but unreliable for constructive claims. The resulting human-AI mathematical contribution, a tight lower bound of $4n(n{-}1)/9$, is achieved via a novel class of near-perfect permutations. The bound was formally verified in Lean 4. Our experiments show that neurosymbolic systems can indeed produce genuine discoveries in pure mathematics.
Problem
Finding tight lower bounds on the imbalance of Latin squares for n congruent to 1 mod 3 has been an open problem in combinatorial design theory.
Approach
The paper documents a human-AI collaboration where an LLM agent, coupled with symbolic computation tools (SageMath, Lean) and human strategic direction, discovers a new result. The process involved the LLM proposing constructions and conjectures, the human directing strategy, and symbolic tools verifying candidates. Lean is used to formalize and certify the final bound. The collaboration spanned multiple sessions over several days.
Results
The collaboration produced a tight lower bound on the imbalance of Latin squares for the case n congruent to 1 mod 3. The paper reconstructs the discovery process from interaction logs and identifies distinct cognitive contributions of each participant: the LLM for rapid exploration and pattern matching, symbolic tools for verification, and the human for strategic redirection.