Technical Summary: Mapping Uncharted Symmetries via Machine Discovery in Combinatorics

Problem Formulation

The paper addresses a specific class of mathematical discovery problems framed as function discovery: given two sets $X$ and $Y$, find a function $f: X \to Y$ that satisfies rigid, exact constraints while admitting a simple, symbolic description. The authors formalize this setting as Simple Learning Under Rigid Proportions (SLURP).

In SLURP, the domain $X$ is partitioned into "bags" $B_i$, and each bag is associated with a target distribution $D_i$ on the codomain $Y$. The objective is to discover a function $f$ such that:

1. Rigid Proportion Constraint: The outputs of $f$ on each bag $B_i$ match the target distribution $D_i$ exactly. Approximate satisfaction is insufficient; any deviation implies the problem is unsolved.
2. Simplicity Requirement: The function must be provided as a concise symbolic description (closed formula or algorithm) that is evaluable within a reasonable time bound (e.g., polynomial). This requirement is fundamental to ensure the solution reveals mathematical structure rather than being a trivial, arbitrary assignment of values.

The authors apply this framework to algebraic combinatorics, specifically the study of $q,t$-Narayana polynomials $N_{n,k}(q,t)$. The core challenge is to find pairs of simple statistics (functions) on combinatorial objects (noncrossing partitions) that jointly generate these polynomials and to construct explicit bijections that prove their symmetry $N_{n,k}(q,t) = N_{n,k}(t,q)$.

Methodology

The paper introduces two distinct machine learning methods to solve SLURP instances:

1. MapSeek-Functional (Self-Training Approach)

This method models the desired function using a neural network (specifically a Transformer encoder) and alternates between two steps:

• Constraint Projection: Given the current model $f_\theta$, the algorithm finds the closest function $\hat{f}$ that satisfies the rigid proportion constraints exactly. This involves solving an optimization problem to minimize the distance between $f_\theta$ and the constraint-satisfying function.
• Supervised Update: The projected function $\hat{f}$ generates pseudo-labels, which are used to update $f_\theta$ via supervised training (SGD).
• Validation: A strict stopping criterion is enforced: a run is only successful if the model perfectly satisfies the constraints on a validation set. The size of the validation set acts as a hyperparameter to filter out complex or non-interpretable solutions.
• Distillation: Post-convergence, the neural network's behavior is manually or automatically distilled into a symbolic formula.

2. MapSeek-Symbolic (Search Approach)

This method directly searches for symbolic formulas within a defined formal language $\mathcal{L}$.

• Search Space: Formulas are constructed from an alphabet of primitive symbols (variables, arithmetic operators, logical operators).
• Optimization: The search employs a Deep Cross-Entropy Method (CEM) using a generative Transformer decoder. It iteratively samples a population of formulas, evaluates their "distance" (violation of constraints), and selects an elite subset to retrain the generative model.
• Distance Metric: The distance function $\delta$ measures the $L_1$ difference between the output distribution of a candidate formula and the target distribution. The authors found that treating the problem as a classification task (using a trivial metric) was more effective than a regression approach (using sorted $L_1$ distance).
• Stability: The authors noted that explicit structural delimiters (whitespace and parentheses) in the formula notation were crucial for training stability, preventing the model from generating syntactically valid but semantically redundant expressions.

Key Contributions and Results

1. The SLURP Framework and Benchmark

The authors formalize the SLURP framework and release the skip-pairing benchmark. This benchmark tasks the discovery of statistics on noncrossing partitions that pair with the known "skip" statistic to interpret $q,t$-Narayana polynomials. The dataset includes refined constraints based on the maximum element in non-singleton blocks.

2. Discovery of New Statistics

Applying both methods to the case $k=3$ (partitions with $n-2$ blocks), the authors discovered several new, interpretable statistics:

• Mag (Magnitude): Discovered via MapSeek-Functional with warm-start constraints. It pairs with the skip statistic.
• Leap: Discovered via MapSeek-Functional with homogeneity constraints. It pairs with the skip statistic.
• Skew: Discovered via MapSeek-Symbolic. It pairs with the skip statistic.
• Mingarc (Min Gap Arc): A human-defined extension of the flipped "skew" statistic, derived from the ML discoveries.

3. Solving an Open Problem in Combinatorics

The most significant mathematical result is the solution to Open Problem 4.1 for the case $k=3$:

• Combinatorial Proof of Symmetry: The authors constructed an explicit exchanging bijection that maps a partition $\pi$ to $\psi(\pi)$ such that the pair of statistics $(\text{skip}, \text{leap})$ is exchanged: $(\text{skip}(\psi(\pi)), \text{leap}(\psi(\pi))) = (\text{leap}(\pi), \text{skip}(\pi))$.
• This provides the first combinatorial proof of the symmetry $N_{n,3}(q,t) = N_{n,3}(t,q)$ via an explicit bijection, a problem widely regarded as extremely difficult.
• New Interpretation: The work provides the first combinatorial interpretation of $N_{n,k}(q,t)$ for all $k$ in terms of noncrossing partitions (specifically via the $(\text{skip}, \text{mingarc})$ pairing).

4. Formal Verification

To ensure reproducibility and rigor, the authors formalized all mathematical discoveries, including the new statistics, the bijections, and the symmetry proofs, in Lean 4. They utilized the Aristotle system to assist in autoformalization and proof search, resulting in a fully machine-checked verification of the core results.

Significance and Claims

The paper claims to be the first to use machine learning to propose previously unknown combinatorial statistics that are subsequently used to construct an exchanging bijection solving an open problem in $q,t$-combinatorics.

• Methodological Significance: The authors position SLURP as a "proof-driven discovery framework." Unlike standard machine learning which seeks approximate generalization, SLURP requires exact constraint satisfaction on finite data, with the ultimate goal of finding simple symbolic descriptions that can be mathematically proven to hold on infinite domains.
• Scientific Impact: The work demonstrates that modern ML can meaningfully contribute to verifiable mathematical discoveries, specifically in finding simple functions under rigid distributional constraints.
• Limitations and Future Work: The authors modestly note that while the $k=3$ case yielded closed-form solutions, the $k=4$ experiments currently show failure modes (e.g., MapSeek-Functional converging to hard-to-interpret solutions, MapSeek-Symbolic failing to reach zero distance). They acknowledge that understanding the exploration of the solution space and quantifying "simplicity" remain open methodological challenges.

The paper concludes that these tools, in the hands of expert mathematicians, can leverage human intuition to extend the reach of mathematical discovery, particularly in areas where constructing explicit bijections is a primary bottleneck.