Mapping Uncharted Symmetries: Machine Discovery in Combinatorics
Eugenio Cainelli, Lorenzo Luccioli, Alessandro Iraci, Michele D'Adderio, Giovanni Paolini
cs.LG
May 18, 2026 · v1
TL;DR
Formalizes in Lean 4 the new combinatorial interpretation and symmetry proof of q,t-Narayana polynomials.
Abstract
Inspired by long-standing open problems in algebraic combinatorics, we show that modern machine learning can meaningfully contribute to verifiable mathematical discoveries. In particular, we focus on the construction of simple mathematical functions under exact distributional constraints, a setting we formalize as Simple Learning Under Rigid Proportions (SLURP). We tackle this problem by introducing two methods: MapSeek-Functional, which models the desired function alternating pseudo-labeling and supervised training steps; and MapSeek-Symbolic, designed to directly produce symbolic formulas. We successfully apply both methods to a research problem in algebraic combinatorics, discovering a new combinatorial interpretation of the $q,t$-Narayana polynomials arising from representation theory. To our knowledge, this is the first such interpretation based on noncrossing partitions. Using one discovered statistic, we find a combinatorial proof of the symmetry of these polynomials in a previously unsolved case. To streamline verification and reproducibility, we release all code, including a formalization of all the mathematical discoveries of this paper in Lean 4.
Problem
Open problems in algebraic combinatorics require discovering simple mathematical functions satisfying exact distributional constraints, particularly finding combinatorial interpretations of q,t-polynomials like the Narayana polynomials. Existing approaches have not leveraged machine learning for this type of exact combinatorial function discovery.
Approach
The authors introduce Simple Learning Under Rigid Proportions (SLURP), a learning framework where the goal is to find a simple function matching specified output distributions exactly. They propose two methods: MapSeek-Functional, which uses a Transformer encoder alternating pseudo-labeling and supervised training, and MapSeek-Symbolic, which directly produces symbolic formulas. Both are applied to discover new combinatorial statistics on noncrossing partitions that pair with the skip statistic to interpret q,t-Narayana polynomials. All mathematical discoveries are formalized in Lean 4.
Results
The methods discover a new combinatorial interpretation of the q,t-Narayana polynomials based on noncrossing partitions, which to the authors' knowledge is the first such interpretation. Using one discovered statistic, they find a combinatorial proof of the symmetry of these polynomials for the case k=3, solving a previously open problem. All code and Lean 4 formalizations are released.
