Discovering a Zeta Map Algorithm on Dyck Paths via Mechanistic Interpretability

# Discovering a Zeta Map Algorithm on Dyck Paths via Mechanistic Interpretability
Source: [https://arxiv.org/html/2605.30482](https://arxiv.org/html/2605.30482)
###### Abstract

Machine learning is increasingly used in mathematical discovery, but in mathematics the desired output is often not a prediction itself, but an explicit construction that can be checked independently\. We study this setting through the zeta map on Dyck paths, a classical bijection in the combinatorics of theq,tq,t\-Catalan numbers\. We train a deliberately small one\-layer, one\-head encoder–decoder transformer on this map and analyze its learned computation using mechanistic interpretability tools, including decoder cross\-attention analysis, linear probing, and causal intervention\. The analysis reveals a level\-based mechanism: encoder representations make path levels linearly accessible, while the decoder selects and traverses input positions in a structured way\. Translating these signals into combinatorics leads to the*scaffolding map*, an explicit peak\-centered traversal algorithm for Dyck paths\. We prove that this algorithm agrees with the zeta map, modulo a reversal convention in the labeling\. This gives a controlled example of AI\-assisted mathematical discovery in which mechanistic interpretability turns model behavior into a precise, human\-verifiable combinatorial algorithm\.

AI for mathematics, human\-AI collaboration, AI\-assisted discovery, combinatorics, Dyck paths, zeta map, transformers, mechanistic interpretability

## 1Introduction

Machine learning is increasingly used in mathematical research\(Gukov et al\.,[2021](https://arxiv.org/html/2605.30482#bib.bib13); Charton et al\.,[2024](https://arxiv.org/html/2605.30482#bib.bib8); Novikov et al\.,[2025](https://arxiv.org/html/2605.30482#bib.bib20)\), but many successful applications still treat a model primarily as a high\-accuracy predictor or generative model\. For mathematical discovery, prediction alone is typically insufficient: the desired output is often a conjecture, construction, or explicit algorithm that a mathematician can verify\. This paper studies such a human\-AI workflow in a concrete combinatorial setting, the zeta map on Dyck paths\. We train transformer models\(Vaswani et al\.,[2017](https://arxiv.org/html/2605.30482#bib.bib25)\)on a known mathematical bijection, interpret the mechanism learned by a deliberately small transformer via mechanistic interpretability tools, and extract from this interpretation a new explicit algorithm\.

The zeta map is a central combinatorial object in the theory ofq,tq,t\-Catalan numbers because it gives a bijective explanation for the symmetry between the standard Dyck\-path statistics appearing in the formulas forq,tq,t\-Catalan numbers\. In particular, it converts the\(dinv,area\)\(\\mathrm\{dinv\},\\mathrm\{area\}\)description into the\(area,bounce\)\(\\mathrm\{area\},\\mathrm\{bounce\}\)description, linking two different definitions\(Haglund,[2003](https://arxiv.org/html/2605.30482#bib.bib14); Haiman,[2000](https://arxiv.org/html/2605.30482#bib.bib15)\)\. Since the zeta map already admits several algorithmic descriptions\(Andrews et al\.,[2002](https://arxiv.org/html/2605.30482#bib.bib2); Haglund,[2003](https://arxiv.org/html/2605.30482#bib.bib14)\), it provides an ideal test case for AI\-assisted mathematical discovery: the data are exactly generable, correctness can be checked exhaustively at moderate sizes, and the desired output is a discrete combinatorial procedure rather than a numerical approximation\.

We first show that transformers can learn the zeta map across several experimental settings\. We then reduce the architecture to a one\-layer, one\-head encoder–decoder transformer, for which the learned solution is sufficiently structured to analyze mechanistically\. The central quantity revealed by this analysis is the level sequence of the input Dyck path: cross\-attention suggests that the decoder selects positions according to level, causal ablations show that many upward\-step positions are not directly needed during decoding, and linear probes show that level information is recoverable from encoder representations\. These observations led us to formulate the*scaffolding map*, a peak\-centered traversal algorithm for Dyck paths\. Unlike the classical area\-sequence descriptions of the zeta map, this procedure is organized directly in terms of levels and local traversal\. To the best of our knowledge, this is a first example of using mechanistic interpretation of a trained neural sequence model to extract a new explicit bijective description of a well\-studied combinatorial map\.

A broader goal of this paper is to use the zeta map as a proving ground for AI in combinatorics research, namely to demonstrate the ability to discover combinatorial bijections and algorithms from trained models\. While the precise details may differ from one application of AI in math to another, the concepts articulated in this paper are widely applicable within combinatorics research\. The model supplies recurring structural signals; the human investigator interprets these signals as combinatorial operations; additional interventions test whether the interpretation is causally relevant; and the resulting procedure becomes a mathematical object that can be stated and proved independently of the neural network\.

## 2Related Work

#### AI\-Assisted Discovery\.

AI methods have shown increasing promise as search tools for mathematical discovery\. Reinforcement\-learning approaches have been used to find explicit examples and counterexamples in extremal combinatorics, graph theory, and knot theory\(Wagner,[2021](https://arxiv.org/html/2605.30482#bib.bib26); Gukov et al\.,[2021](https://arxiv.org/html/2605.30482#bib.bib13)\)\. More recent work further studies how reinforcement\-learning agents navigate difficult mathematical search spaces with sparse high\-reward instances\(Butbaia et al\.,[2026](https://arxiv.org/html/2605.30482#bib.bib7); Fagan et al\.,[2026](https://arxiv.org/html/2605.30482#bib.bib11)\)\. Complementary generative model\-guided search and LLM\-based coding agents have also been used to discover extremal mathematical structures and improved algorithms\(Charton et al\.,[2024](https://arxiv.org/html/2605.30482#bib.bib8); Bérczi et al\.,[2026](https://arxiv.org/html/2605.30482#bib.bib5); Novikov et al\.,[2025](https://arxiv.org/html/2605.30482#bib.bib20)\)\. Our work differs in focus: rather than using AI to search for examples, we use mechanistic interpretability to extract an explicit combinatorial algorithm from a trained model\.

#### Mechanistic Interpretability\.

Mechanistic interpretability seeks to reverse engineer the algorithms implemented by trained neural networks\. Relevant precedents in mathematical settings include analyses of small transformers trained on modular arithmetic and group operations\(Nanda et al\.,[2023](https://arxiv.org/html/2605.30482#bib.bib19); Chughtai et al\.,[2023](https://arxiv.org/html/2605.30482#bib.bib9); Zhong et al\.,[2023](https://arxiv.org/html/2605.30482#bib.bib30)\)and arithmetic and enumerative geometry tasks\(Babei et al\.,[2025](https://arxiv.org/html/2605.30482#bib.bib4); Hashemi et al\.,[2025](https://arxiv.org/html/2605.30482#bib.bib16)\)\. There are recent efforts on automating discovery such as automated circuit discovery\(Conmy et al\.,[2023](https://arxiv.org/html/2605.30482#bib.bib10)\), automated neuron or feature explanation\(Bills et al\.,[2023](https://arxiv.org/html/2605.30482#bib.bib6); Shaham et al\.,[2024](https://arxiv.org/html/2605.30482#bib.bib22)\), and activation\-to\-language decoding methods\(Pan et al\.,[2026](https://arxiv.org/html/2605.30482#bib.bib21); Karvonen et al\.,[2026](https://arxiv.org/html/2605.30482#bib.bib18)\)\.

## 3Mathematical Background

### 3\.1Dyck paths andq,tq,t\-Catalan statistics

Dyck paths are fundamental objects in combinatorics\. A*Dyck word*of semilengthnnis a binary wordw=\(wi\)i=12​nw=\(w\_\{i\}\)\_\{i=1\}^\{2n\}of length2​n2nconsisting of exactlynn11’s such that every initial segment contains at least as many11’s as0’s\. We writeDyck​\(n\)\\mathrm\{Dyck\}\(n\)for the set of such words where\|Dyck​\(n\)\|\\lvert\\mathrm\{Dyck\}\(n\)\\rvertis the well\-knownnnth Catalan number\. Equivalently, by interpreting11as a North step and0as an East step, a*Dyck path*is a lattice path from\(0,0\)\(0,0\)to\(n,n\)\(n,n\)that stays weakly above the diagonaly=xy=x, with an example shown in[Figure1](https://arxiv.org/html/2605.30482#S3.F1)\.

![Refer to caption](https://arxiv.org/html/2605.30482v1/pics/example.png)Figure 1:An example of Dyck path of semilength55\.Theq,tq,t\-Catalan numbers refine the Catalan numbers and admit two Dyck\-path expansions involving the statisticsarea\\mathrm\{area\},bounce\\mathrm\{bounce\}, anddinv\\mathrm\{dinv\}:

Cn​\(q,t\)\\displaystyle C\_\{n\}\(q,t\)=∑w∈Dyck​\(n\)qarea​\(w\)​tbounce​\(w\)\\displaystyle=\\sum\_\{w\\in\\mathrm\{Dyck\}\(n\)\}q^\{\\mathrm\{area\}\(w\)\}t^\{\\mathrm\{bounce\}\(w\)\}=∑w∈Dyck​\(n\)qdinv​\(w\)​tarea​\(w\)\.\\displaystyle=\\sum\_\{w\\in\\mathrm\{Dyck\}\(n\)\}q^\{\\mathrm\{dinv\}\(w\)\}t^\{\\mathrm\{area\}\(w\)\}\.\{\}\(1\)These formulas were discovered independently by\(Haglund,[2003](https://arxiv.org/html/2605.30482#bib.bib14); Haiman,[2000](https://arxiv.org/html/2605.30482#bib.bib15)\)\. Herearea​\(w\)\\mathrm\{area\}\(w\)counts the cells between the path and the diagonal,bounce​\(w\)\\mathrm\{bounce\}\(w\)is computed from Haglund’s bounce path, anddinv​\(w\)\\mathrm\{dinv\}\(w\)counts certain diagonal inversions in the area sequence ofww\.

The equivalence of the two definitions motivates the search for a bijection that exchanges these statistics\. Haglund’s zeta map\(Haglund,[2003](https://arxiv.org/html/2605.30482#bib.bib14)\)is a bijectionζ\\zeta, satisfying

\(dinv​\(w\),area​\(w\)\)=\(area​\(ζ​\(w\)\),bounce​\(ζ​\(w\)\)\)\.\(\\mathrm\{dinv\}\(w\),\\mathrm\{area\}\(w\)\)=\(\\mathrm\{area\}\(\\zeta\(w\)\),\\mathrm\{bounce\}\(\\zeta\(w\)\)\)\.Although the zeta map is unique, it has several combinatorial interpretations, including descriptions in terms of area sequences\(Andrews et al\.,[2002](https://arxiv.org/html/2605.30482#bib.bib2); Haglund,[2003](https://arxiv.org/html/2605.30482#bib.bib14)\)and the sweep map\(Armstrong et al\.,[2015](https://arxiv.org/html/2605.30482#bib.bib3); Thomas & Williams,[2018](https://arxiv.org/html/2605.30482#bib.bib24)\), which describes its inverse\. We do not aim to replace these interpretations\. Instead, we ask whether a model trained on the map can reveal an alternative algorithmic organization\. We include further background on theq,tq,t\-Catalan numbers and the zeta map in[AppendixA](https://arxiv.org/html/2605.30482#A1)\.

For a Dyck wordw=\(wi\)i=12​nw=\(w\_\{i\}\)\_\{i=1\}^\{2n\}, we define its level sequence byℓ0=0\\ell\_\{0\}=0and

ℓi=\{ℓi−1\+1,if​wi=1,ℓi−1−1,if​wi=0\.\\ell\_\{i\}=\\begin\{cases\}\\ell\_\{i\-1\}\+1,&\\text\{ if \}w\_\{i\}=1,\\\\ \\ell\_\{i\-1\}\-1,&\\text\{ if \}w\_\{i\}=0\.\\end\{cases\}Levels later become a central latent combinatorial quantity identified by our interpretability analysis\.

## 4Experimental Setup

#### Experiments\.

For fixed semilengthnn, we construct a supervised dataset of Dyck words and their images\. More precisely, for each input Dyck wordww, the target sequence is the image produced by theSageMath\(The Sage Developers,[2026](https://arxiv.org/html/2605.30482#bib.bib23)\)functionarea\_dinv\_to\_bounce\_area\_map\(\)\. Under the labeling convention used by this function, discussed further in[AppendixD](https://arxiv.org/html/2605.30482#A4), the target agrees withrev∘ζ​\(w\)\\mathrm\{rev\}\\circ\\zeta\(w\), whererev\\mathrm\{rev\}denotes reading the Dyck word backward and swapping0’s and11’s\.

Using a fixed architecture with an embedding dimension of256256, 4 encoder layers, and 4 decoder layers \(each with 8 attention heads\), the models achieved\>99%\>99\\%accuracy in learning the zeta map, that is, predicting the image of a Dyck path under the zeta map for datasets of semilengthsn=11,12,13,14,15,16n=11,12,13,14,15,16, with sizes58,78658\{,\}786,208,012208\{,\}012,742,900742\{,\}900,2,674,4402\{,\}674\{,\}440,9,694,8459\{,\}694\{,\}845, and35,357,67035\{,\}357\{,\}670, corresponding to the Catalan numbersCnC\_\{n\}\.

We later varied the architecture and the hyperparameters and explored with a selective subset of

- •encoder\-only, decoder\-only, and encoder–decoder architectures;
- •the number of transformer layers, ranging from 1 to 4;
- •the number of attention heads, ranging from 1 to 8,

and the model was able to obtain near perfect accuracy for almost all settings\.

#### Compression\.

We then trained a minimal model with embedding dimension128128, one encoder layer, one decoder layer, and one attention head\. The model has339,716339\{,\}716parameters and achieved perfect or near\-perfect accuracy across repeated runs\. This model trained on then=13n=13dataset, which we call the*Minimal Dyck Transformer*, is the focus of the interpretability analysis below\. We include architectural details of*Minimal Dyck Transformer*in[AppendixB](https://arxiv.org/html/2605.30482#A2)\.

## 5Interpreting the Minimal Dyck Transformer

### 5\.1Cross\-attention patterns

While several mechanistic inspections reveal useful structure, as shown in[AppendixC](https://arxiv.org/html/2605.30482#A3), the most informative internal signal is decoder cross\-attention\. We dynamically track, at each generation step, which input positions receive the largest decoder cross\-attention weights\. An example is shown in[Figure2](https://arxiv.org/html/2605.30482#S5.F2)\. During generation, the decoder repeatedly attends to a small and structured subset of input positions\. Across examples, we observe three recurring patterns\.

![Refer to caption](https://arxiv.org/html/2605.30482v1/pics/xattn_example_wide.png)Figure 2:Representative decoder cross\-attention matrices for theMinimal Dyck Transformer\. The recurring sparse patterns indicate that generation is organized by level\-based selection rather than by an unstructured lookup table\.#### Highest\-level selection\.

At early output steps, most prominently observed in the attention visualization when the decoder generates the first step of the output Dyck word, the decoder places attention on input positions whose levels are maximal among relevant positions\. An example can be seen in[Figure3\(a\)](https://arxiv.org/html/2605.30482#S5.F3.sf1)and[3\(b\)](https://arxiv.org/html/2605.30482#S5.F3.sf2)\. This suggests that level information has already been computed by the encoder and is being used by the decoder as a selection criterion\.

![Refer to caption](https://arxiv.org/html/2605.30482v1/pics/dyck_ex.png)\(a\)
![Refer to caption](https://arxiv.org/html/2605.30482v1/pics/step1_xattn_ex.png)\(b\)
![Refer to caption](https://arxiv.org/html/2605.30482v1/x1.png)\(c\)

Figure 3:Example of decoder cross\-attention and its causal role\. Left: input, target, and model\-generated Dyck paths, with attended input positions highlighted in yellow\. Middle: sparse cross\-attention used when generating the first output step on the left\. Right: causal ablation results showing negligible decreases in accuracy, measured by comparing the generated output path with the correct target path up to thekkth step, after ablating all cross\-attention to input North steps\.
#### Systematic avoidance of many upward steps\.

Positions withwi=1w\_\{i\}=1receive no cross\-attention throughout decoding, hence the decoder cannot directly “read off” level and direction information from upward steps: ignoringwi=1w\_\{i\}=1prevents the model from directly accessing the upward steps’ levels and directions\. One way for the decoder to compare information of such positions is that the encoder has already aggregated and stored them in the hidden states of thewi=0w\_\{i\}=0positions\. However, we show this is not the case in[Section5\.2](https://arxiv.org/html/2605.30482#S5.SS2)\. Instead, it appears to rely heavily on selected positions and reconstructs the rest through a structured traversal\.

#### Triangular sequential shift\.

As decoding proceeds, many examples exhibit the triangular attention pattern shown in[Figure2](https://arxiv.org/html/2605.30482#S5.F2)\. This pattern suggests that, after selecting a high\-level positioniiwith East\-step \(wi=0w\_\{i\}=0\), the model often shifts attention to the next eligible positioni\+1i\+1also with East\-step\. By the Dyck path structure, this position satisfiesℓi\+1=ℓi−1\\ell\_\{i\+1\}=\\ell\_\{i\}\-1, indicating that the model moves rightward through nearby positions with sequentially decreasing levels\.

### 5\.2Ablation and probing

We next test whether these visual patterns correspond to functionally relevant structure\.

#### Causal ablation\.

We mask cross\-attention to input positions withwi=1w\_\{i\}=1during decoding\. This causal intervention causes only a negligible degradation in accuracy shown in[Figure3\(c\)](https://arxiv.org/html/2605.30482#S5.F3.sf3), supporting the hypothesis that many upward\-step positions are not essential carriers of decoding\-time information\.

#### Linear probing\.

We train linear probes\(Alain & Bengio,[2016](https://arxiv.org/html/2605.30482#bib.bib1)\)from encoder hidden states to the corresponding level valuesℓi\\ell\_\{i\}\. The probes recover level information with high predictive accuracy of 84%, indicating that the encoder representation makes this combinatorial statistic linearly accessible\. This supports a two\-stage interpretation: the encoder computes level\-like information, and the decoder uses it to select and traverse positions\.

These observations suggest that the model is not memorizing the zeta map as an arbitrary lookup table\. Instead, it appears to organize generation by levels, starting from peaks and then traversing nearby positions\. Abstracting this behavior led us to the following explicit procedure, which we call the*scaffolding map*\.

## 6The Scaffolding Map

We now state the algorithm suggested by the*Minimal Dyck Transformer*\. Letw=\(wi\)i=12​nw=\(w\_\{i\}\)\_\{i=1\}^\{2n\}be a Dyck word, and compute levelsℓi\\ell\_\{i\}as above\. Let

R=\{i∈\{1,…,2​n\}:wi=0\}R=\\\{i\\in\\\{1,\\ldots,2n\\\}:w\_\{i\}=0\\\}be the set of East\-step positions\. A*peak position*is an indexiisuch that\(wi,wi\+1\)=\(1,0\)\(w\_\{i\},w\_\{i\+1\}\)=\(1,0\)\.

Informally, the algorithm starts from peaks at high levels and releases two types of agents that move along adjacent East\-step and non\-East\-step positions\. Reading the symbols encountered by these agents, level by level from top to bottom, produces the output word\.

#### Scaffolding map\.

1. 1\.Group peak positions by their levelℓi\\ell\_\{i\}\.
2. 2\.Initializeout=\[\]\\textit\{out\}=\[\\,\],agents=\[\]\\textit\{agents\}=\[\\,\], and set the current level to the maximum level of any peak\.
3. 3\.While\|out\|<2​n\|\\textit\{out\}\|<2n: 1. \(a\)Letqueuebe the union of the current agents and the peak positions at the current level\. 2. \(b\)Sortqueuein decreasing order\. For eachiiin the queue in this order, appendwiw\_\{i\}toout\. 3. \(c\)Update all existing agents simultaneously\. If an agent is at a positioniiinRR, move it toi\+1i\+1when this is a valid position inRR; otherwise remove it\. If an agent is at a positioniinot inRR, move it toi−1i\-1when this is a valid position not inRR; otherwise remove it\. 4. \(d\)For each peakjjat the current level, spawn new agents atj\+1j\+1ifj\+1∈Rj\+1\\in Rand atj−1j\-1ifj−1∉Rj\-1\\notin R, when valid\. 5. \(e\)Decrease the current level by11\.
4. 4\.Returnout\.

We call this the*scaffolding map*because the upward steps build the level structure, while the output is generated by agents traversing this scaffold from peak positions\. The name emphasizes the separation between the latent support structure and the subsequent traversal\. Although the transformer is trained at a fixed semilengthnn, the resulting*scaffolding map*is defined uniformly for Dyck paths of all semilengths\.

###### Theorem 6\.1\.

The scaffolding map is equivalent to the zeta map up to a reversal convention in the labeling\. Precisely, denote the scaffolding map byφ\\varphi\. Definerev\\mathrm\{rev\}to be flipping the Dyck path with respect toy=−xy=\-x, or reading the Dyck word backward with0and11swapped\. Then

φ=rev∘ζ\.\\varphi=\\mathrm\{rev\}\\circ\\zeta\.

The full proof is provided in[AppendixD](https://arxiv.org/html/2605.30482#A4)\. The proof strategy is to compare the scaffolding map with the area\-sequence description ofrev∘ζ\\mathrm\{rev\}\\circ\\zetalevel by level\. The model\-derived algorithm is therefore not presented as a replacement for proof, but as a source of a precise theorem whose verification can be completed by standard combinatorial arguments\.

## 7Discussions

#### Summary\.

This work uses the zeta map on Dyck paths as a controlled test case for AI\-assisted mathematical discovery\. By compressing the model to a minimal one\-head encoder–decoder transformer, we obtain a learned solution whose internal structure can be inspected directly\. The resulting attention, causal ablation, and probing evidence point to a level\-based computation, which we translate into the scaffolding map: an explicit peak\-centered traversal algorithm for Dyck paths\. This illustrates a workflow in which a neural model is not the final mathematical object, but a source of structured evidence that guides the formulation of a new theorem\.

#### Limitations\.

The present study has several limitations\. First, attention patterns alone are not proof of mechanism\(Jain & Wallace,[2019](https://arxiv.org/html/2605.30482#bib.bib17); Wiegreffe & Pinter,[2019](https://arxiv.org/html/2605.30482#bib.bib29)\); this is why we pair them with causal ablations, probes, and an independent combinatorial formulation\. Second, the transformer we interpret appears to implement a “fuzzy” version of the scaffolding algorithm\. This is reflected, for example, in the imperfect level\-probing results\. The learned mechanism may become cleaner with longer training, as observed in related settings\(Nanda et al\.,[2023](https://arxiv.org/html/2605.30482#bib.bib19)\)\. More importantly, the scaffolding map was extracted from a particularly simple trained model\. Larger models may implement complicated algorithms, and we also observe even small models may admit multiple internal solutions across random seeds\(Zhong et al\.,[2023](https://arxiv.org/html/2605.30482#bib.bib30); Wen et al\.,[2023](https://arxiv.org/html/2605.30482#bib.bib27)\)\.

#### Future Directions\.

Future work could automate more of this discovery loop and adapt it to larger, less transparent models\. Automated circuit\-discovery methods and interpretability agents\(Conmy et al\.,[2023](https://arxiv.org/html/2605.30482#bib.bib10); Friedman et al\.,[2023](https://arxiv.org/html/2605.30482#bib.bib12); Shaham et al\.,[2024](https://arxiv.org/html/2605.30482#bib.bib22)\), together with activation\-to\-language methods\(Pan et al\.,[2026](https://arxiv.org/html/2605.30482#bib.bib21); Karvonen et al\.,[2026](https://arxiv.org/html/2605.30482#bib.bib18)\), could help identify recurring internal mechanisms and translate them into candidate symbolic rules\. Coupling these tools with theorem provers may further support the transition from model\-derived hypotheses to formally verified combinatorial algorithms\.

## References

- Alain & Bengio \(2016\)Alain, G\. and Bengio, Y\.Understanding intermediate layers using linear classifier probes\.*arXiv preprint arXiv:1610\.01644*, 2016\.
- Andrews et al\. \(2002\)Andrews, G\., Krattenthaler, C\., Orsina, L\., and Papi, P\.ad\-Nilpotent b\-Ideals in sl\(n\) Having a Fixed Class of Nilpotence: Combinatorics and Enumeration\.*Transactions of the American Mathematical Society*, 354\(10\):3835–3853, 2002\.ISSN 0002\-9947\.URL[https://www\.jstor\.org/stable/3072985](https://www.jstor.org/stable/3072985)\.Publisher: American Mathematical Society\.
- Armstrong et al\. \(2015\)Armstrong, D\., Loehr, N\., and Warrington, G\.Sweep maps: A continuous family of sorting algorithms\.*Advances in Mathematics*, 284:159–185, 2015\.
- Babei et al\. \(2025\)Babei, A\., Charton, F\., Costa, E\., Huang, X\., Lee, K\.\-H\., Lowry\-Duda, D\., Narayanan, A\., and Pozdnyakov, A\.Learning euler factors of elliptic curves, 2025\.
- Bérczi et al\. \(2026\)Bérczi, G\., Hashemi, B\., and Klüver, J\.Flow\-based extremal mathematical structure discovery\.*arXiv preprint arXiv:2601\.18005*, 2026\.
- Bills et al\. \(2023\)Bills, S\., Cammarata, N\., Mossing, D\., Tillman, H\., Gao, L\., Goh, G\., Sutskever, I\., Leike, J\., Wu, J\., and Saunders, W\.Language models can explain neurons in language models\.[https://openaipublic\.blob\.core\.windows\.net/neuron\-explainer/paper/index\.html](https://openaipublic.blob.core.windows.net/neuron-explainer/paper/index.html), 2023\.
- Butbaia et al\. \(2026\)Butbaia, G\., Orland, P\., Huang, X\., Passaro, D\., Fagan, L\., Tarquini, M\., Dao, H\., Eisenbud, D\., Shehper, A\., and Gukov, S\.Hierarchical reinforcement learning for sparse\-reward search in commutative algebra\.In*Forty\-third International Conference on Machine Learning*, 2026\.URL[https://openreview\.net/forum?id=DF6jVG4fG8](https://openreview.net/forum?id=DF6jVG4fG8)\.
- Charton et al\. \(2024\)Charton, F\., Ellenberg, J\., Wagner, A\., and Williamson, G\.Patternboost: Constructions in mathematics with a little help from ai, 2024\.
- Chughtai et al\. \(2023\)Chughtai, B\., Chan, L\., and Nanda, N\.A toy model of universality: Reverse engineering how networks learn group operations\.In*International Conference on Machine Learning*, pp\. 6243–6267\. PMLR, 2023\.
- Conmy et al\. \(2023\)Conmy, A\., Mavor\-Parker, A\., Lynch, A\., Heimersheim, S\., and Garriga\-Alonso, A\.Towards automated circuit discovery for mechanistic interpretability\.*Advances in Neural Information Processing Systems*, 36:16318–16352, 2023\.
- Fagan et al\. \(2026\)Fagan, L\., Tarquini, M\., Shehper, A\., Manko, M\., Huang, X\., Gruen, A\., Butbaia, G\., Passaro, D\., and Gukov, S\.The two\-hump problem: Bridging the difficulty gap in mathematical reinforcement learning\.In*Forty\-third International Conference on Machine Learning*, 2026\.URL[https://openreview\.net/forum?id=PUQ0rrmuDM](https://openreview.net/forum?id=PUQ0rrmuDM)\.
- Friedman et al\. \(2023\)Friedman, D\., Wettig, A\., and Chen, D\.Learning transformer programs\.*Advances in Neural Information Processing Systems*, 36:49044–49067, 2023\.
- Gukov et al\. \(2021\)Gukov, S\., Halverson, J\., Ruehle, F\., and Sułkowski, P\.Learning to unknot\.*Machine Learning: Science and Technology*, 2\(2\):025035, 2021\.
- Haglund \(2003\)Haglund, J\.Conjectured statistics for theq,t\-Catalan numbers\.*Advances in Mathematics*, 175\(2\):319–334, May 2003\.ISSN 0001\-8708\.doi:10\.1016/S0001\-8708\(02\)00061\-0\.URL[https://www\.sciencedirect\.com/science/article/pii/S0001870802000610](https://www.sciencedirect.com/science/article/pii/S0001870802000610)\.
- Haiman \(2000\)Haiman, M\.The q,t–Catalan Numbers and the Alternating Component of the Diagonal Harmonics\.Preprint, University of California, Berkeley, 2000\.
- Hashemi et al\. \(2025\)Hashemi, B\., Corominas, R\., and Giacchetto, A\.Can transformers do enumerative geometry?In*International Conference on Learning Representations*, volume 2025, pp\. 70047–70067, 2025\.
- Jain & Wallace \(2019\)Jain, S\. and Wallace, B\. C\.Attention is not explanation, 2019\.URL[https://arxiv\.org/abs/1902\.10186](https://arxiv.org/abs/1902.10186)\.
- Karvonen et al\. \(2026\)Karvonen, A\., Chua, J\., Dumas, C\., Fraser\-Taliente, K\., Kantamneni, S\., Minder, J\., Ong, E\., Sharma, A\. S\., Wen, D\., Evans, O\., and Marks, S\.Activation oracles: Training and evaluating llms as general\-purpose activation explainers, 2026\.URL[https://arxiv\.org/abs/2512\.15674](https://arxiv.org/abs/2512.15674)\.
- Nanda et al\. \(2023\)Nanda, N\., Chan, L\., Lieberum, T\., Smith, J\., and Steinhardt, J\.Progress measures for grokking via mechanistic interpretability, 2023\.
- Novikov et al\. \(2025\)Novikov, A\., Vũ, N\., Eisenberger, M\., Dupont, E\., Huang, P\.\-S\., Wagner, A\. Z\., Shirobokov, S\., Kozlovskii, B\., Ruiz, F\. J\., Mehrabian, A\., et al\.Alphaevolve: A coding agent for scientific and algorithmic discovery\.*arXiv preprint arXiv:2506\.13131*, 2025\.
- Pan et al\. \(2026\)Pan, A\., Chen, L\., and Steinhardt, J\.Latentqa: Teaching llms to decode activations into natural language, 2026\.URL[https://arxiv\.org/abs/2412\.08686](https://arxiv.org/abs/2412.08686)\.
- Shaham et al\. \(2024\)Shaham, T\. R\., Schwettmann, S\., Wang, F\., Rajaram, A\., Hernandez, E\., Andreas, J\., and Torralba, A\.A multimodal automated interpretability agent\.In*Forty\-first International Conference on Machine Learning*, 2024\.
- The Sage Developers \(2026\)The Sage Developers\.*SageMath, the Sage Mathematics Software System \(Version 9\.5\)*, 2026\.https://www\.sagemath\.org\.
- Thomas & Williams \(2018\)Thomas, H\. and Williams, N\.Sweeping up zeta\.*Selecta Mathematica*, 24\(3\):2003–2034, 2018\.
- Vaswani et al\. \(2017\)Vaswani, A\., Shazeer, N\., Parmar, N\., Uszkoreit, J\., Jones, L\., Gomez, A\., Kaiser, Ł\., and Polosukhin, I\.Attention is all you need\.*Advances in neural information processing systems*, 30, 2017\.
- Wagner \(2021\)Wagner, A\. Z\.Constructions in combinatorics via neural networks, 2021\.URL[https://arxiv\.org/abs/2104\.14516](https://arxiv.org/abs/2104.14516)\.
- Wen et al\. \(2023\)Wen, K\., Li, Y\., Liu, B\., and Risteski, A\.Transformers are uninterpretable with myopic methods: a case study with bounded dyck grammars, 2023\.URL[https://arxiv\.org/abs/2312\.01429](https://arxiv.org/abs/2312.01429)\.
- Wennberg & Henter \(2024\)Wennberg, U\. and Henter, G\.Learned transformer position embeddings have a low\-dimensional structure\.In*Proceedings of the 9th workshop on representation learning for NLP \(RepL4NLP\-2024\)*, pp\. 237–244, 2024\.
- Wiegreffe & Pinter \(2019\)Wiegreffe, S\. and Pinter, Y\.Attention is not not explanation, 2019\.URL[https://arxiv\.org/abs/1908\.04626](https://arxiv.org/abs/1908.04626)\.
- Zhong et al\. \(2023\)Zhong, Z\., Liu, Z\., Tegmark, M\., and Andreas, J\.The clock and the pizza: Two stories in mechanistic explanation of neural networks, 2023\.

## Appendix Aq,tq,t\-Catalan Numbers and the Zeta Map

### A\.1q,tq,t\-Catalan Numbers

We start this section by defining the main objects of interest, Dyck paths\.

###### Definition A\.1\.

A Dyck path of semilengthnnis a length2​n2nbinary sequencew=\(wi\)i=1,…,2​nw=\(w\_\{i\}\)\_\{i=1,\\ldots,2n\}with the property that each initial segment\(wi\)i=1,…,k;k≤2​n\(w\_\{i\}\)\_\{i=1,\\ldots,k;\\ k\\leq 2n\}ofwwcontains at least as many11’s as0’s\. We denote the set of all Dyck paths of semilengthnnbyD​y​c​k​\(n\)Dyck\(n\)\.

###### Remark A\.2\.

Equivalently, a Dyck path of semilengthnnis a lattice path from\(0,0\)\(0,0\)to\(n,n\)\(n,n\)consisting of North\(0,1\)\(0,1\)and East\(1,0\)\(1,0\)steps that stays on or above the liney=xy=x\. Under this equivalence, a11in the binary representation corresponds to a North step, and a0corresponds to an East step\. We will usewwto refer to the binary sequence and lattice path representation of a Dyck path interchangeably\.

It is well known that the number of Dyck paths of semilengthnnis thennth Catalan number

Cn=1n\+1​\(2​nn\)\.C\_\{n\}=\\frac\{1\}\{n\+1\}\{2n\\choose n\}\.
There is another equivalent formalization of Dyck paths in terms of the number of complete boxes between the lattice path representation of a Dyck path and the diagonaly=xy=xin each row, from bottom to top, which is convenient for calculating the statistics in Theorem 1\.

###### Definition A\.3\.

The area sequence of a Dyck pathwwof semilengthnnis the sequence\(ai\)i=1,…,n\(a\_\{i\}\)\_\{i=1,\\ldots,n\}whereaia\_\{i\}counts the number of complete boxes in rowiibetween the Dyck path and the diagonaly=xy=x, where the rows are enumerated from bottom to top\.

Every Dyck pathwwuniquely determines an area sequence\(ai\)\(a\_\{i\}\)and vice versa\. An example of the lattice path, binary sequence, and area sequence representations of a Dyck path is given in Example 1\.

We now define the three statistics which appear in[Equation1](https://arxiv.org/html/2605.30482#S3.E1)\.

###### Definition A\.4\.

Letw=\(wi\)w=\(w\_\{i\}\)be a Dyck path of semilengthnnand\(ai\)\(a\_\{i\}\)be its area sequence\. The area ofwwis the nonnegative integer

a​r​e​a​\(w\)=∑i=1nai\.area\(w\)=\\sum\_\{i=1\}^\{n\}a\_\{i\}\.The dinv \(or diagonal inversion\) ofwwis the nonnegative integer

d​i​n​v​\(w\)=\#​\{\(i,j\)\|i<j,ai=aj\}\+\#​\{\(i,j\)\|i<j,ai=aj\+1\}\.dinv\(w\)=\\\#\\\{\(i,j\)\\ \|\\ i<j,a\_\{i\}=a\_\{j\}\\\}\+\\\#\\\{\(i,j\)\\ \|\\ i<j,a\_\{i\}=a\_\{j\}\+1\\\}\.

###### Definition A\.5\.

Letw=\(wi\)w=\(w\_\{i\}\)be a Dyck path of semilengthnn\. The bounce ofwwis the nonnegative integer calculated in the following way:

1. 1\.Shoot a billiard from\(0,0\)\(0,0\)heading North
2. 2\.When you hit the start of an East step, turn East and travel until you hit the diagonal
3. 3\.Turn North and repeat until you reach\(n,n\)\(n,n\)\.
4. 4\.Record the places you hit the diagonal\(0,0\),\(j1,j1\),…,\(jk,jk\),\(n,n\)\(0,0\),\(j\_\{1\},j\_\{1\}\),\\ldots,\(j\_\{k\},j\_\{k\}\),\(n,n\)\.

Then

b​o​u​n​c​e​\(w\)=∑i=1k\(n−ji\)\.bounce\(w\)=\\sum\_\{i=1\}^\{k\}\(n\-j\_\{i\}\)\.

###### Definition A\.6\.

Thent​hn^\{th\}q,tq,t\-Catalan number is

Cn​\(q,t\)=∑w∈D​y​c​k​\(n\)qa​r​e​a​\(w\)​tb​o​u​n​c​e​\(w\)=∑w∈D​y​c​k​\(n\)qd​i​n​v​\(w\)​ta​r​e​a​\(w\)∈ℤ\>0​\[q,t\]\.C\_\{n\}\(q,t\)=\\sum\_\{w\\in Dyck\(n\)\}q^\{area\(w\)\}t^\{bounce\(w\)\}=\\sum\_\{w\\in Dyck\(n\)\}q^\{dinv\(w\)\}t^\{area\(w\)\}\\in\\mathbb\{Z\}\_\{\>0\}\[q,t\]\.

### A\.2Haglund’s Zeta Map

The zeta map uses the area sequence/bounce path\(Andrews et al\.,[2002](https://arxiv.org/html/2605.30482#bib.bib2); Haglund,[2003](https://arxiv.org/html/2605.30482#bib.bib14)\), and can be described by the following algorithm:

1. 1\.Compute the area sequencea1,a2,…,ana\_\{1\},a\_\{2\},\\ldots,a\_\{n\}ofww\(row lengths from bottom\)\.
2. 2\.Setb=max​\{ai\}\+1b=\\text\{max\}\\\{a\_\{i\}\\\}\+1\.
3. 3\.For eachk=0,1,…,bk=0,1,\\ldots,b, scan the sequencea1,a2,…,ana\_\{1\},a\_\{2\},\\ldots,a\_\{n\}from left to right and record: 1. \(a\)a0for each occurrence ofk−1k\-1, 2. \(b\)a11for each occurrence ofkk\. Since the area sequence contains no entries equal to−1\-1orbb, this procedure starts with a11whenk=0k=0and ends with a0whenk=bk=b\.

Below is an example of the image of the zeta map of a Dyck path of semilength 8\.

###### Example A\.7\.

Consider the Dyck pathwwbelow\.

The area sequence is\(0,1,2,2,2,3,1,2\)\(0,1,2,2,2,3,1,2\)\. Scanning from left to right for−1\-1and0, we find no occurrence of−1\-1, and the single occurrence of0produces11in the image under the zeta map\. Next, scanning for0and11, we obtain the subsequence0,1,10,1,1, which yields0,1,10,1,1in the image\. Scanning for11and22gives1,2,2,2,1,21,2,2,2,1,2, producing0,1,1,1,0,10,1,1,1,0,1\. Similarly, scanning for22and33yields2,2,2,3,22,2,2,3,2, which produces0,0,0,1,00,0,0,1,0\. Finally, scanning for33and44gives33, producing0\.

⟶\\longrightarrow⟶\\longrightarrow⟶\\longrightarrow⟶\\longrightarrow

## Appendix BArchitecture of Minimal Dyck Transformer

We use a deliberately small encoder–decoder transformer\. The goal is to keep architectural capacity minimal while still permitting explicit inspection of attention patterns\.

#### Model specification\.

The model is a standard encoder–decoder transformer without dropout:

- •Embedding/model width:dmodel=128d\_\{\\text\{model\}\}=128\.
- •Feed\-forward width:dff=256d\_\{\\text\{ff\}\}=256with GELU nonlinearity\.
- •Layers:11encoder block and11decoder block\.
- •Attention heads:11\.
- •Dropout:0\.
- •Maximum length: positional embeddings defined up tomax\_len=128\\texttt\{max\\\_len\}=128\.

It has approximately3\.66×1053\.66\\times 10^\{5\}trainable parameters\.

#### Token and positional embeddings\.

For a token sequence\(x1,…,xL\)\(x\_\{1\},\\dots,x\_\{L\}\), the encoder input is

𝐇=Embeds​r​c\(x1:L\)\+PosEmbed\(1:L\),\\mathbf\{H\}=\\mathrm\{Embed\}\_\{src\}\(x\_\{1:L\}\)\+\\mathrm\{PosEmbed\}\(1\{:\}L\),and the decoder input is defined similarly, using a distinct target embedding tableEmbedt​g​t\\mathrm\{Embed\}\_\{tgt\}\. Positional encodings are*learned*, i\.e\., given by an embedding lookup indexed by position; sinusoidal encoding is disabled in this configuration\.

#### Attention mechanism\.

All attention sublayers use scaled dot\-product attention\. For queriesQQ, keysKK, and valuesVV,

Attn​\(Q,K,V\)=softmax​\(Q​K⊤dhead\)​V\.\\mathrm\{Attn\}\(Q,K,V\)=\\mathrm\{softmax\}\\\!\\left\(\\frac\{QK^\{\\top\}\}\{\\sqrt\{d\_\{\\text\{head\}\}\}\}\\right\)V\.Decoder*self\-attention*is causal: when no mask is explicitly provided, an upper\-triangular causal mask is applied to prevent attention to future target positions\. Encoder self\-attention and decoder cross\-attention are non\-causal\.

#### Transformer blocks \(post\-norm\)\.

Each encoder block applies self\-attention and a position\-wise feed\-forward network with residual connections and*post\-layer normalization*:

𝐇←LN​\(𝐇\+SelfAttn​\(𝐇\)\),𝐇←LN​\(𝐇\+FFN​\(𝐇\)\)\.\\mathbf\{H\}\\leftarrow\\mathrm\{LN\}\\\!\\big\(\\mathbf\{H\}\+\\mathrm\{SelfAttn\}\(\\mathbf\{H\}\)\\big\),\\quad\\mathbf\{H\}\\leftarrow\\mathrm\{LN\}\\\!\\big\(\\mathbf\{H\}\+\\mathrm\{FFN\}\(\\mathbf\{H\}\)\\big\)\.Each decoder block applies \(i\) causal self\-attention, \(ii\) encoder–decoder cross\-attention, and \(iii\) the same FFN, each followed by residual addition and post\-norm:

𝐙←LN​\(𝐙\+SelfAttncausal​\(𝐙\)\),𝐙←LN​\(𝐙\+CrossAttn​\(𝐙,𝐇e​n​c\)\),𝐙←LN​\(𝐙\+FFN​\(𝐙\)\)\.\\mathbf\{Z\}\\leftarrow\\mathrm\{LN\}\\\!\\big\(\\mathbf\{Z\}\+\\mathrm\{SelfAttn\}\_\{\\text\{causal\}\}\(\\mathbf\{Z\}\)\\big\),\\;\\mathbf\{Z\}\\leftarrow\\mathrm\{LN\}\\\!\\big\(\\mathbf\{Z\}\+\\mathrm\{CrossAttn\}\(\\mathbf\{Z\},\\mathbf\{H\}\_\{enc\}\)\\big\),\\;\\mathbf\{Z\}\\leftarrow\\mathrm\{LN\}\\\!\\big\(\\mathbf\{Z\}\+\\mathrm\{FFN\}\(\\mathbf\{Z\}\)\\big\)\.The FFN is

FFN​\(𝐱\)=W2​GELU​\(W1​𝐱\+b1\)\+b2,\\mathrm\{FFN\}\(\\mathbf\{x\}\)=W\_\{2\}\\,\\mathrm\{GELU\}\(W\_\{1\}\\mathbf\{x\}\+b\_\{1\}\)\+b\_\{2\},withW1∈ℝ128×256W\_\{1\}\\in\\mathbb\{R\}^\{128\\times 256\}andW2∈ℝ256×128W\_\{2\}\\in\\mathbb\{R\}^\{256\\times 128\}\.

#### Output head\.

Decoder hidden states are mapped to next\-token logits by a linear projectionℝ128→ℝ4\\mathbb\{R\}^\{128\}\\rightarrow\\mathbb\{R\}^\{4\}applied at each position\. No weight tying is used between the embeddings and the output projection\.

## Appendix COther Embedding And Attention Visualizations

In this section, we present some visualizations that were helpful when investigating the internal mechanism of the transformer\.

#### Additional Cross\-Attention Examples\.

We include additional examples illustrating the three recurring attention patterns, showing that they are common phenomena rather than hand\-picked examples: highest\-level selection, systematic avoidance of many positions withwi=1w\_\{i\}=1, and triangular sequential shift\.

![Refer to caption](https://arxiv.org/html/2605.30482v1/pics/xattn_batch.png)Figure 4:Cross\-attention matrices at a fixed output step2323generation for a batch of random samples, illustrating that the triangular shift pattern occurs consistently across examples\.![Refer to caption](https://arxiv.org/html/2605.30482v1/pics/level_attention.png)Figure 5:Level\-attention comparison across examples\. Decoder cross\-attention at the first output step consistently concentrates on high\-level input positions\.
#### Encoder self\-attention\.

Beyond decoder cross\-attention, we also inspect encoder self\-attention to understand how the model organizes input positions before decoding\. The resulting attention maps show recurring block\-like structure partly due to the binary nature of Dyck paths\.

![Refer to caption](https://arxiv.org/html/2605.30482v1/pics/encoder_attn.png)Figure 6:Encoder self\-attention matrices across a batch of examples\. The recurring block\-like structure reflects the binary organization of Dyck words and suggests that the encoder forms structured position\-level representations\.
#### Learned positional embeddings\.

We further visualize the learned encoder and decoder positional embeddings using PCA\. These plots show that the model learns nontrivial positional geometry: for the encoder embeddings, the first principal component separates early positions from the main cluster, while the second principal component largely follows the ordering of input positions\. This ordered geometry may help explain the block\-like structure observed in the encoder attention maps\. Since nearby positions have similar positional embeddings, their position\-dependent contributions to attention are similar; consequently, much of the remaining variation in the attention pattern is driven by the binary token value,0or11\. This combination of smooth positional variation and token\-level separation naturally produces block\-like attention structure\.

![Refer to caption](https://arxiv.org/html/2605.30482v1/pics/encoder_pos_emb.png)Figure 7:PCA of the learned encoder positional embeddings\. The second principal component largely follows the ordering of input positions, while the first component separates some early positions from the main cluster\.![Refer to caption](https://arxiv.org/html/2605.30482v1/pics/decoder_pos_emb.png)Figure 8:PCA of the learned decoder positional embeddings\. Decoder positions form a more regular spiral trajectory in the first two principal components\(Wennberg & Henter,[2024](https://arxiv.org/html/2605.30482#bib.bib28); Vaswani et al\.,[2017](https://arxiv.org/html/2605.30482#bib.bib25)\)\.

## Appendix DProof of the Scaffolding–Zeta Equivalence

To begin with, we clarify conventions and fix notations\.

Our scaffolding map, denoted byφ\\varphi, coincides witharea\_dinv\_to\_bounce\_area\_map\(\)inSageMath, which we used to generate our datasets\. However, it does not agree with Haglund’s zeta map, denoted byζ\\zeta, due to a difference in conventions: the bounce path is defined in the reverse direction inSageMathcompared to Haglund’s formulation\. In this section, we prove

φ=rev∘ζ,\\varphi=\\mathrm\{rev\}\\circ\\zeta,whererev\\mathrm\{rev\}is reading the Dyck word backward with0and11swapped\.

Leta​\(w\)=\(a1,a2,…,an\)a\(w\)=\(a\_\{1\},a\_\{2\},\\dots,a\_\{n\}\)be the area sequence of a Dyck pathww, and setb=max​\{ai\}\+1b=\\text\{max\}\\\{a\_\{i\}\\\}\+1\. Recall the algorithm forζ\\zetadescribed at the beginning of Section[A\.2](https://arxiv.org/html/2605.30482#A1.SS2)\.

For eachk=0,1,…,bk=0,1,\\ldots,b, scan the sequencea1,a2,…,ana\_\{1\},a\_\{2\},\\ldots,a\_\{n\}from left to right and record:

1. 1\.a0for each occurrence ofk−1k\-1,
2. 2\.a11for each occurrence ofkk\.

Accordingly, an algorithm forrev∘ζ\\mathrm\{rev\}\\circ\\zetais given by the following\.

For eachk=b,b−1,…,0k=b,b\-1,\\ldots,0, scan the sequencea1,a2,…,ana\_\{1\},a\_\{2\},\\ldots,a\_\{n\}from right to left and record:

1. 1\.a0for each occurrence ofkk,
2. 2\.a11for each occurrence ofk−1k\-1\.

From the algorithm ofrev∘ζ\\mathrm\{rev\}\\circ\\zeta, for eachk=b,b−1,…,0k=b,b\-1,\\ldots,0, we obtain a subsequencePkP\_\{k\}ofa~​\(w\)\\tilde\{a\}\(w\)consisting ofkkandk−1k\-1, wherea~​\(w\)=\(an,an−1,…,a1\)\\tilde\{a\}\(w\)=\(a\_\{n\},a\_\{n\-1\},\\dots,a\_\{1\}\)\. \(Recall that we scana​\(w\)a\(w\)from right to left in the algorithm ofrev∘ζ\\mathrm\{rev\}\\circ\\zeta\.\) For example, the Dyck path in Example[A\.7](https://arxiv.org/html/2605.30482#A1.Thmtheorem7)\(see[Figure9](https://arxiv.org/html/2605.30482#A4.F9)below\) yields

P4=\(3\),P3=\(2,3,2,2,2\),P2=\(2,1,2,2,2,1\),P1=\(1,1,0\),P0=\(0\)\.P\_\{4\}=\(3\),\\quad P\_\{3\}=\(2,3,2,2,2\),\\quad P\_\{2\}=\(2,1,2,2,2,1\),\\quad P\_\{1\}=\(1,1,0\),\\quad P\_\{0\}=\(0\)\.These subsequences completely determine the image ofrev∘ζ\\mathrm\{rev\}\\circ\\zeta\.

On the other hand, in the algorithm of the scaffolding mapφ\\varphidescribed in Section[6](https://arxiv.org/html/2605.30482#S6), eachwiw\_\{i\}ofw=\(wi\)w=\(w\_\{i\}\)is associated with levelℓi\\ell\_\{i\},1≤i≤2​n1\\leq i\\leq 2n\. Define

bi=\{ℓi−1if​wi=1,ℓiif​wi=0\.b\_\{i\}=\\begin\{cases\}\\ell\_\{i\}\-1&\\text\{if \}w\_\{i\}=1,\\\\ \\ell\_\{i\}&\\text\{if \}w\_\{i\}=0\.\\end\{cases\}For each1≤i≤2​n1\\leq i\\leq 2n, we associate positioniiwithara\_\{r\}for somerrina​\(w\)=\(a1,…,an\)a\(w\)=\(a\_\{1\},\\dots,a\_\{n\}\)in the following way; in particular, we will havebi=arb\_\{i\}=a\_\{r\}\.

Ifwi=1w\_\{i\}=1and positioniibelongs to therthr^\{\\mathrm\{th\}\}row, then we associate positioniiwithara\_\{r\}and havebi=ℓi−1=arb\_\{i\}=\\ell\_\{i\}\-1=a\_\{r\}\. Ifwi=0w\_\{i\}=0, then we slide with slope11down to the south\-west direction until we hit a position, sayjj, withwj=1w\_\{j\}=1\. Suppose that positionjjbelongs to therthr^\{\\mathrm\{th\}\}row\. Then we associate positioniiwithara\_\{r\}and obtainbi=ℓi=arb\_\{i\}=\\ell\_\{i\}=a\_\{r\}from the symmetry of rows and columns, noting thatbib\_\{i\}is equal to the length of the column that contains positionii\. For example, in Example[A\.7](https://arxiv.org/html/2605.30482#A1.Thmtheorem7), position 10, marked with×\\times, is associated witha5=2a\_\{5\}=2, and position 11, marked with∘\\circ, is associated witha2=1a\_\{2\}=1\.

×\\timesFigure 9:Dyck path with marked positions used in the proof\.In step \(3\)\(a\) of the scaffolding algorithm, the queuesQb,Qb−1,…,Q0Q\_\{b\},Q\_\{b\-1\},\\dots,Q\_\{0\}are formed, whereb=max⁡\{ℓi\}=max⁡\{ai\}\+1b=\\max\\\{\\ell\_\{i\}\\\}=\\max\\\{a\_\{i\}\\\}\+1as before\. Fork=b,b−1,…,0k=b,b\-1,\\dots,0, eachQkQ\_\{k\}consists of positionsi1,i2,…i\_\{1\},i\_\{2\},\\dots\. Replace them with the correspondingbi1,bi2,…b\_\{i\_\{1\}\},b\_\{i\_\{2\}\},\\dots, and denote the resulting sequence byQk′Q^\{\\prime\}\_\{k\}\. For example, in Example[A\.7](https://arxiv.org/html/2605.30482#A1.Thmtheorem7), we have

Q4=\(8\),Q3=\(13,9,7,5,3\),Q2=\(14,12,10,6,4,2\),Q1=\(15,11,1\),Q0=\(16\),\\displaystyle Q\_\{4\}=\(8\),\\quad Q\_\{3\}=\(13,9,7,5,3\),\\quad Q\_\{2\}=\(14,12,10,6,4,2\),\\quad Q\_\{1\}=\(15,11,1\),\\quad Q\_\{0\}=\(16\),Q4′=\(3\),Q3′=\(2,3,2,2,2\),Q2′=\(2,1,2,2,2,1\),Q1′=\(1,1,0\),Q0′=\(0\)\.\\displaystyle Q^\{\\prime\}\_\{4\}=\(3\),\\quad Q^\{\\prime\}\_\{3\}=\(2,3,2,2,2\),\\quad Q^\{\\prime\}\_\{2\}=\(2,1,2,2,2,1\),\\quad Q^\{\\prime\}\_\{1\}=\(1,1,0\),\\quad Q^\{\\prime\}\_\{0\}=\(0\)\.The sequencesQkQ\_\{k\}, or the sequencesQk′Q^\{\\prime\}\_\{k\}determine the image of the scaffolding mapϕ\\phi\.

We now claim thatPk=Qk′P\_\{k\}=Q^\{\\prime\}\_\{k\}fork=b,b−1,…,0k=b,b\-1,\\dots,0\. Indeed, in eachPkP\_\{k\}, the occurrences ofk−1k\-1correspond to entriesbi=k−1b\_\{i\}=k\-1inQk′Q^\{\\prime\}\_\{k\}, arising from peaks or positionsi∉Ri\\notin RinQkQ\_\{k\}; the occurrences ofkkcorrespond to positionsi∈Ri\\in R, wherebi=k=arb\_\{i\}=k=a\_\{r\}, and therthr^\{\\mathrm\{th\}\}row is associated withiias described above in the penultimate paragraph\.

SincePkP\_\{k\}andQk′Q^\{\\prime\}\_\{k\}determine the images ofrev∘ζ\\mathrm\{rev\}\\circ\\zetaandϕ\\phi, respectively, the claim implies thatrev∘ζ=ϕ\\mathrm\{rev\}\\circ\\zeta=\\phi, as desired\.