Machine search for combinatorial bijections has hit two walls. A bijection here is an explicit one-to-one map between families of discrete objects, such as lattice paths or set partitions, that carries one numerical feature (a "statistic") to another. The first wall is reward hacking: evolutionary program synthesizers "solve" bijection tasks with index lookups or brute force. The second is a scalability wall: symbolic search found a hidden statistic that settled one open symmetry case, but failed on the next case, where short closed-form formulas seem to vanish. We propose to search instead over formulas of logics from descriptive complexity. That field matches syntactic resources in logic (quantifiers, counting, bounded recursion) exactly to circuit resources (depth, gate type). Candidates are then tried in order of how much parallel computation they need. A single formula must work at every object size, so lookup tables cannot even be written down. When search fails at one level, the failure is itself informative: no map of that computational strength exists within a given formula size.
The two-sentence version is this. Combinatorial statistics like area, inversions, or leap are almost always "count the tuples satisfying a small first-order condition," and harder ones like bounce need recursion of logarithmic depth. So a search language whose rungs are exactly these descriptive-complexity levels should rediscover known bijections cheaply, be unable to hack the reward, and tell us whether the frontier cases (the $k=4$ Narayana symmetry, the area–bounce swap) are hard because they need more depth or merely more size.
Core Claim
We claim that the right hypothesis space for bijection and statistic discovery is a sequence of logics, each a proper step up in circuit depth, rather than arbitrary Python or unstructured arithmetic expressions. We further claim that the $k=4$ failure reported by Mapping Uncharted Symmetries: Machine Discovery in Combinatorics reflects a missing depth rung, not missing size. That paper resolved the $k=3$ case of the $q,t$-Narayana symmetry $N_{n,k}(q,t)=N_{n,k}(t,q)$ by discovering leap and a Lean-verified bijection exchanging it with skip. Its authors conjecture that at $k=4$ "more complex algorithmic solutions" replace closed forms. Descriptive complexity makes this conjecture testable. An "algorithmic" statistic may still be a short formula once bounded recursion is allowed, just as Simulating Logspace-Recursion with Logarithmic Quantifier Depth showed that sequential logspace recursion can be rebalanced into formulas of logarithmic quantifier depth.
The ladder has four rungs, built from existing characterizations. Rung 0 contains counting statistics of the form "number of $r$-tuples of positions satisfying a first-order formula $\varphi$." A model-theoretic characterization of constant-depth arithmetic circuits shows that counting winning strategies or Skolem witnesses of first-order formulas captures exactly $\#AC^0$, the functions computed by constant-depth polynomial-size circuits with plus and times gates. Descriptive Complexity of #AC0 Functions introduced the Skolem-counting view. Rung 1 adds counting quantifiers, which gives $TC^0$ (constant depth with majority gates) via the same paper's $TC^0 = AC^0\#AC^0$ result. Rungs 2 and 3 add guarded predicative recursion from Model-Theoretic Characterization of Boolean and Arithmetic Circuit Classes of Small Depth. In that recursion, each step may only call itself on a parameter at most half the current one, so it bottoms out after $\log n$ steps. Its bounded form captures $NC^1$ and its full form $AC^1$. Bijections are expressed as first-order interpretations, meaning formulas that define each output symbol from the input. For example, "step $i$ of the output Dyck path is Up iff $\psi(i)$ holds."
Research Program
The first component is the language and an exact evaluator. Objects are encoded as ordered finite structures. A Dyck path is a word of length $2n$ with order and letter predicates. A noncrossing partition is the set $[n]$ with order and a same-block relation. A typed grammar generates formulas at each rung. We evaluate each candidate statistic on all objects up to a size $n_{\max}$ and compare its joint distribution with the target statistic bag by bag, as in the Skip-Pairing setup. Candidate bijections are checked for validity, injectivity and exchange of statistics, which mirrors the three metrics of the OpenEvolve suite. The fitness of a formula is the total joint-distribution discrepancy summed over every $n$ from 4 to $n_{\max}$. The formula is fixed across sizes, so any accepted candidate is uniform by construction. We will also score it on two held-out larger sizes it never saw during search.
The second component is search. We use exhaustive enumeration by formula size up to a budget, pruning formulas that agree on all small structures. Above that budget we use a Transformer-guided cross-entropy method, reusing the MapSeek-Symbolic procedure of Mapping Uncharted Symmetries but with our grammar in place of its arithmetic alphabet. This keeps the search engine constant, so any gain comes from the hypothesis space. The rungs are searched in order. Moving up is triggered only after the lower rung is exhausted at the size budget.
The third component is a complexity census of known bijections, which calibrates the ladder. We will hand-write formulas and prove upper bounds for the Catalan bijections collected in Bijections Between Standard Young Tableaux and Classical Combinatorics Structures of Catalan Numbers, which link $(n,n)$ tableaux, Dyck paths, binary trees, noncrossing partitions and stack-sortable permutations. We will do the same for skip, leap, area, dinv and bounce. Where possible we will also prove unconditional lower bounds. If the parity of a statistic computes the parity of a subset of input bits, that statistic is not first-order definable, because parity lies outside $AC^0$. We will not claim separations of $TC^0$ from $NC^1$, which remain open. For those rungs we report only upper bounds together with empirical non-discovery within stated size budgets.
Baselines
The naive reference point is size-ordered brute-force enumeration of Python programs over the same object encodings, with the same fitness and evaluation budget. It measures how much any structured grammar helps at all.
The strongest existing method on the Narayana question is MapSeek-Symbolic from Mapping Uncharted Symmetries. It is the only system reported to have solved an open case, and it "consistently converged to the leap statistic across multiple runs" on the $N_{14,3}$ benchmark. That benchmark has 2,366 partitions in 144 skip-bags. The paper gives no success rate or compute figure; no reported result found on Lacuna for MapSeek-Symbolic's run count or wall-clock on $N_{14,3}$. We will rerun its released code with the same number of candidate evaluations and the same hardware as our system. Beating it means two things. On $k=3$, recovering leap or an equivalent statistic in fewer evaluations with at least equal reliability over seeds. On $k=4$, finding any exact partner statistic where it finds none.
For the Dyck-path suite, the strongest baseline is OpenEvolve from Even with AI, Bijection Discovery is Still Hard. It reported rediscovering the odd-diagonal-avoiding bijection "after approximately 60 iterations," failing on 321-avoiding permutations, and reverting to brute force on area–bounce. We will run it with the same LLM-call budget converted to candidate evaluations. Beating it means solving problem 2 with a uniform map that survives the held-out sizes, and matching or beating its 60 iterations on problem 1.
Two ablations isolate the key ingredients. The first keeps the full grammar but drops the rung ordering and searches the union at once with an equal budget. This tests whether grading by depth matters or only the logical vocabulary does. The second allows separate formulas per $n$, which tests whether enforcing uniformity is what blocks reward hacking.
Why not just…?
Why not just prove the symmetries with generating functions? Analytic proofs establish that $N_{n,k}(q,t)$ is symmetric but produce neither a statistic nor a map. The $k=3$ case stayed open until the explicit leap statistic was found (Mapping Uncharted Symmetries). Our targets are explicit maps, so generating functions complement this work rather than compete with it. They can supply correctness checks for any conjectured distribution.
Why not just give OpenEvolve more compute or better prompts? Its reported failures are qualitative: lookup-style hacking, defaulting to familiar algorithms such as stack sorting, and brute force on the open problem (Even with AI, Bijection Discovery is Still Hard). More compute does not remove any of these. Still, the compute-matched rerun, plus a second arm at four times the budget, will show directly whether scale alone closes the gap on 321-avoiding permutations.
Why not just search Python with a program-length penalty? This is the real threat. A length prior might supply most of the benefit without any logic. The naive baseline with a length penalty, and the unordered-grammar ablation, test it directly. If a length-penalized Python search matches our $k=3$ and problem-2 results at equal budget, the depth-grading claim fails, and we would report it as such. The census would then remain as the contribution.
Why not just use least-fixed-point logic, which is simpler and more familiar? On ordered structures it captures all of polynomial time. That admits sequential simulations of arbitrary algorithms, including the brute-force behavior we aim to exclude, and the search space becomes too large to explore. Its failure to isolate low-depth classes is exactly why Model-Theoretic Characterization of Boolean and Arithmetic Circuit Classes of Small Depth and L-Recursion and a new Logic for Logarithmic Space introduce resource-bounded recursion. We include a fixed-point rung as a top-level arm to measure the cost.
Proposed Experiments and Decisive Checks
The first check is calibration. Every census bijection and statistic should be rediscovered at the rung where we can prove it lies, and not below. If leap needs recursion to be found although our proof places it at rung 0, the grammar is miscalibrated.
The second check is the $k=3$ comparison against MapSeek-Symbolic on $N_{14,3}$, measuring evaluations to first exact hit over ten seeds and generalization to $n=15,16$.
The third check covers OpenEvolve problems 1 and 2 under matched budgets, scoring surjectivity, injectivity and validity at held-out sizes.
The decisive experiment is $k=4$. We search for a partner statistic to skip on $NC(n,4)$, rung by rung. There are three possible outcomes. Success at rung 2 or 3 would support the depth hypothesis and give a candidate for Lean formalization following the $k=3$ pipeline. Success at rung 0 or 1 would show MapSeek's alphabet, not depth, was the bottleneck. Exhaustion of all rungs at the size budget would produce a documented statement: no exchanging statistic exists at these complexity levels within that formula size.
We run area–bounce on the same protocol as an exploratory target. We expect the negative-result form of the output to be the likely deliverable there.
We do not use CombiBench (CombiBench). It measures theorem proving on competition problems, not map discovery.
References
- Mapping Uncharted Symmetries: Machine Discovery in Combinatorics
- Simulating Logspace-Recursion with Logarithmic Quantifier Depth
- A Model-Theoretic Characterization of Constant-Depth Arithmetic Circuits
- Descriptive Complexity of #AC0 Functions
- Model-Theoretic Characterization of Boolean and Arithmetic Circuit Classes of Small Depth
- Bijections Between Standard Young Tableaux and Classical Combinatorics Structures of Catalan Numbers
- Even with AI, Bijection Discovery is Still Hard: The Opportunities and Challenges of OpenEvolve for Novel Bijection Construction
- L-Recursion and a new Logic for Logarithmic Space
- CombiBench: Benchmarking LLM Capability for Combinatorial Mathematics