A Computational Obstruction to Swapping Area and Dinv: An Automata-Theoretic View of the $q,t$-Catalan Symmetry

Jineon Baek; Byung-Hak Hwang; Joonhyun La; Hongseok Yang

Source-linked AI summary

A Computational Obstruction to Swapping Area and Dinv: An Automata-Theoretic View of the $q,t$-Catalan Symmetry

Jineon Baek, Byung-Hak Hwang, Joonhyun La, Hongseok Yang

arXiv:2609.05005v1Sep 4, 2026math.COcs.CCcs.FLcs.LO

TL;DR

The paper asks which computational mechanisms are required for uniform bijections explaining Dyck-path statistic identities, especially the unresolved area–dinv swap for the q,t-Catalan symmetry. It models bijections as word transformations, introduces WRP to add one unbounded rank sort to polyregular computation, and classifies key Catalan maps within this hierarchy. WRP contains ζ and the height-sweep bijection but excludes ζ^-1 and every semilength-preserving map that swaps area and dinv.

Problem
No explicit, uniform, semilength-preserving bijection is known that swaps area and dinv on every Dyck path to directly explain C_n(q,t)=C_n(t,q).
Method
The paper studies Dyck-path bijections as word-to-word computations and introduces WRP, extending polyregular maps with one weighted global rank sort.
Results
WRP contains ζ and the classical height-sweep bijection, while ζ is not polyregular, ζ^-1 is outside WRP, and no WRP map realises a semilength-preserving area–dinv swap.
Takeaways & Limitations
The rank-sorting mechanism behind ζ is insufficient within WRP to exchange area and dinv, so any direct uniform bijection must use resources beyond one WRP rank-sort layer.
Takeaways & Limitations
WRP is deliberately one-layered: its selection and labeling cannot inspect ranks, and one rank-sort output cannot feed a second rank-sort layer.

Abstract

from arXiv · show

Algebraic combinatorics often seeks bijections that explain identities between distributions object by object. Encoding combinatorial objects as words lets automata theory study such a bijection as a word-to-word computation and measure its memory, input access, and control of output order. This refines existence questions by asking which computational mechanisms a bijection requires. We develop this viewpoint for Dyck paths. Our motivating example is the $q,t$-Catalan polynomial. Let $D_n$ be the set of Dyck paths of semilength $n$, let $D=\bigcup_{n\ge 0}D_n$, and let $area, dinv, bounce \colon D\to\mathbb{N}$ be the standard statistics. Then, \[ C_n(q,t)=\sum_{P\in D_n}q^{area(P)}t^{bounce(P)} =\sum_{P\in D_n}q^{dinv(P)}t^{area(P)}. \] Haglund's zeta map $ζ\colon D\to D$ gives a bijective proof: it preserves semilength and sends $(dinv,area)$ to $(area,bounce)$. By contrast, the full symmetry $C_n(q,t)=C_n(t,q)$ still lacks a direct explanation: no explicit, uniform, semilength-preserving bijection is known that swaps area and dinv on every Dyck path. Polyregular maps from automata theory provide a natural computational starting point, but we prove that neither $ζ$ nor the classical height-sweep bijection witnessing Narayana symmetry is polyregular. The missing mechanism is global ordering by numerical levels whose range grows with the input. We call this a \emph{rank sort} and introduce \emph{weighted-rank polyregular maps} (WRP), extending polyregular maps by one such sort and containing both bijections. Nevertheless, WRP is a proper subclass of deterministic logspace. We prove that $ζ^{-1}$ lies outside WRP and that no WRP map can realise a semilength-preserving area-dinv swap. Thus the rank-sorting strategy behind $ζ$ cannot be extended within WRP to exchange the two statistics.

1 Introduction

The paper studies bijections on Dyck paths as word-to-word computations, asking which automata-theoretic mechanisms explain Catalan statistic identities. It introduces WRP to capture rank sorting, then proves that this mechanism includes key bijections but cannot realise a full area–dinv swap.

Motivation: The paper treats bijections as computations on word encodings, classifying them by memory, input access, and output-order mechanisms.Dyck paths are encoded as balanced U/D words satisfying the prefix condition.
Motivation: The full q,t-Catalan symmetry lacks a known explicit, uniform, semilength-preserving bijection swapping area and dinv on every Dyck path.Haglund’s zeta map explains one related identity by sending dinv to area and area to bounce.
Computational setting: Polyregular maps cannot realise ζ because their finite-state or logical output-order rules lack sorting by unbounded numerical levels.The missing operation is a global rank sort, such as ordering steps by running height.
Computational setting: WRP extends polyregular maps with one weighted global rank sort, retaining atom selection, labeling, and tie-breaking through the underlying MSO-defined order.Assigning equal ranks recovers polyregular maps, so WRP strictly contains PolyReg once ζ is included.
Positive results: WRP contains both the zeta map and the classical height-sweep bijection, while neither is polyregular.The height-sweep map exchanges valleys and double rises and realises Narayana symmetry.
Lower bounds: No semilength-preserving WRP map can swap area and dinv on every Dyck path, even without requiring the map to be bijective.The proof extracts feature tuples that WRP would force to be semilinear, whereas the statistic identities force a nonsemilinear region with a quadratic boundary.
Lower bounds: The paper also proves that ζ^-1 lies outside WRP, showing that WRP-realisability is not preserved under inversion.Together with the no-swap theorem, this gives two principal lower bounds on WRP’s expressive power.

2 Dyck paths, statistics, and named bijections

The paper fixes Dyck-path and area-sequence conventions, defines the principal statistics, and recalls Haglund’s zeta map and related bijections. These definitions establish the encodings and identities used in later computational analyses.

A Dyck path of semilength n is a balanced {U,D}-word whose prefixes contain at least as many U’s as D’s.
The area sequence records the height immediately before each up-step, with area and dinv defined from that sequence.
The step-word encoding represents each path as a length-2n word, and all later map classifications use this encoding for inputs and outputs.
The zeta map scans area-sequence levels and emits U when an entry equals the current level and D when it equals one less.
Haglund’s zeta map is a bijection on D_n, while its output satisfies bounce(ζ(P)) = area(P); an example gives ζ(UUDDUD) = UUDUDD.

3 Established models of word-to-word computation

This section develops the automata-theoretic framework for word transformations, including MSO transductions, deterministic two-way transducers, and polyregular maps. Its key boundary is that standard models use finite-state or MSO output ordering and lack unbounded numerical rank sorting.

The framework studies Catalan maps as partial word transformations whose required behavior is restricted to Dyck inputs.
Realisation requires agreement on every Dyck input but leaves behavior on non-Dyck words unconstrained, separating computation from Dyck-language recognition.
MSO formulas uniformly select input positions or tuples, assign output letters, and specify their output order across words of every length.
Deterministic MSO string transductions are equivalent to deterministic two-way finite-state transducers and are closed under composition.
Polyregular maps with linear output growth collapse to deterministic MSO string transductions, equivalently deterministic two-way finite-state transducers.
Standard models cannot directly sort selected atoms by an unbounded integer statistic such as a Dyck path’s running height.

4 Weighted-rank polyregular maps (WRP)

WRP extends polyregular maps with one global sort by unbounded, weighted atom ranks, capturing zeta and related Catalan bijections while remaining within deterministic logspace. Its one-layer rank-sort model is strictly stronger than PolyReg but cannot realise zeta's inverse or any semilength-preserving area–dinv swap.

Model definition: WRP assigns selected atoms fixed-dimensional integer-vector ranks from weighted scans, then globally sorts their labels by rank with an MSO-defined tie-order.The selection and labelling remain polyregular; the added rank sort is the model’s defining operation.
Position in the hierarchy: The rank-zero fragment of WRP coincides with PolyReg, so PolyReg is contained in WRP.This establishes conservativity of the extension.
Position in the hierarchy: WRP maps are computable in deterministic logarithmic space using O(log n) working memory, with output length O(n^k) and polynomial evaluation time for fixed arity k.The evaluator recomputes selected atoms instead of storing all potential atoms, retaining only position-sized indices and counters.
Position in the hierarchy: WRP is strictly stronger than PolyReg but a proper subclass of deterministic logspace, with zeta witnessing the first strict inclusion.The additional expressive power comes from ordering selected atoms by an unbounded rank rather than from greater output length.
Catalan examples: Zeta and the height-sweep map H belong to WRP and are not polyregular, showing that rank sorting captures distinct Catalan mechanisms beyond PolyReg.Zeta transports area and dinv, while H exchanges valleys and double rises.
Boundaries: No WRP map can satisfy both area–dinv identities, and zeta’s inverse also lies outside WRP, marking limits of the single rank-sort layer.The area–dinv result excludes even semilength-preserving WRP maps that are not bijections; it does not prove that no such bijection exists in any computational model.

5 Classifying the zeta map

The zeta map is realizable by WRP, specifically sRR1, but not by polyregular maps or deterministic two-way finite-state transducers. Its lower bound uses a regular probe on two-pyramid paths, while the separation reflects unbounded rank sorting rather than output growth.

Upper bound: ζ belongs to sRR1 and therefore to WRP under the step-word encoding.The construction creates rank-sorted atoms from up-steps using heights before and after each step.
Upper bound: Additive level sorts are sRR1 maps, so they provide the rank-sorting mechanism used by ζ.They attach additive levels to selected atoms and order them by rank with scan-direction tie-breaking.
Upper bound: The left-to-right additive level sort maps Dyck paths to Dyck paths but is noninjective on D2, whereas the right-to-left version is bijective on every Dn.Specifically, Φν(UUDD) = Φν(UDUD) = UUDD under left-to-right ties.
Lower bound: The two-pyramid criterion applies a regular probe whose membership distinguishes m ≤ n, yielding the lower bound for ζ.The proof uses a linear-growth slice because a polyregular realisation may behave superlinearly on non-Dyck inputs.
Lower bound: ζ is not realised by any polyregular map, and therefore not by any deterministic two-way finite-state transducer or deterministic MSO string transduction.A two-pyramid probe reduces the issue to regularity of an inverse-image language.

6 The height sweep and the Narayana symmetry

The height-sweep map H sorts Dyck-path steps by starting height with right-to-left ties, realizes Narayana symmetry, and lies in sRR1 but outside PolyReg. Its lower bound mirrors the zeta argument with the two pyramid parameters exchanged.

Computational classification: H belongs to sRR1 but is not realised by any polyregular map or deterministic two-way finite-state transducer.The upper bound follows from additive level sorting, while the lower bound uses the two-pyramid probe.
The height-sweep map: H lists steps by increasing starting height and breaks equal-height ties from right to left.It is the additive level sort with ν(U)=+1 and ν(D)=−1 under right-to-left tie-order.
Narayana symmetry: The right-to-left tie-order exchanges valleys and double rises, unlike the left-to-right convention on the same level sort.For UUUDDD, H produces UDUDUD, exchanging val = 0 and dr = 2.
Narayana symmetry: H is a bijection Dn → Dn satisfying dr(H(P)) = val(P) and val(H(P)) = dr(P).Thus H realizes the Narayana symmetry Narn(q,t) = Narn(t,q).
Computational classification: The same regular probe separates H by detecting n ≤ m rather than m ≤ n.The roles of the two parameters are exchanged relative to the zeta-map proof.
Contrast with area–dinv: A single sRR1 rank sort can realize Narayana symmetry, showing that the WRP obstruction to area–dinv swapping is not merely model weakness.The distinction is between this local-statistic symmetry and the stronger q,t-Catalan symmetry.

7 Regular-slice semilinearity for WRP

On the regular family Wn = U(UD)nD, WRP maps with linear output growth produce semilinear first-ascent pairs. This finite-pattern constraint is the structural half of the later no-swap theorem.

Regular slices: The family Wn = U(UD)nD is a regular slice whose repeated-block form exposes finite-state behavior.It has the form uvnz with fixed u = U, v = UD, and z = D.
Role in the no-swap proof: The semilinearity result supplies a finite-union-of-linear-patterns constraint for WRP outputs on this family.The later obstruction will contradict this constraint using a set with a quadratic lower boundary.
Presburger description: WRP output selection, labeling, and ordering on a regular slice are expressible by Presburger formulas.Positions are encoded by a region, a fixed offset, and a repetition index when they lie in the repeated block.
Main theorem: For T ∈ WRP with |T(Wn)| = O(n), the set of first-ascent pairs (fas(T(Wn)), tailU(T(Wn))) is semilinear.Here fas counts U-steps before the first D and tailU counts later U-steps.
Counting and projection: The quantities fas and tailU become counts of selected U-atoms before and after the first selected D-atom.Bounded counting and projection preserve semilinearity, producing the final set of pairs.

8 The family (Wn)n≥1 and the no-swap theorem

The family Wn has statistics that force any semilength-preserving area–dinv swap into rigid deficit-zero targets. Their first-ascent pairs form a nonsemilinear triangular set, contradicting WRP semilinearity and ruling out such swaps within WRP.

Forced targets: For Wn = U(UD)nD, a hypothetical area–dinv swap sends Wn to a deficit-zero path.The equality dinv = coarea is the extreme case of dinv ≤ coarea.
Forced targets: Deficit-zero rigidity uniquely determines each target as an initial staircase followed by a short two-level tail.Its first ascent and later-up-step counts therefore obey an explicit triangular relation.
Triangular obstruction: The first-ascent pairs of the swapped images form exactly the triangular set Stri.The identification follows by expressing the target parameters through a = fas(Qn) and b = tailU(Qn).
Triangular obstruction: Stri is not semilinear because its lower boundary is genuinely quadratic rather than eventually affine on residue classes.This contradicts the eventual-affine lower-envelope behavior of semilinear sets.
No-swap theorem: No WRP map realizes a semilength-preserving area–dinv swap on all Dyck paths.The contradiction combines WRP first-ascent semilinearity with the nonsemilinearity of Stri.
Scope: The theorem does not rule out area–dinv swaps for each fixed semilength; it rules out one uniform WRP map realizing them simultaneously for all semilengths.The q,t-Catalan symmetry still implies that some fixed-n bijection exists.

9 A second separation: inverse zeta lies outside WRP

The paper shows that inverse zeta is not WRP, so WRP-realisability is not preserved under inversion even for semilength-preserving Dyck-path bijections.

Semilinearity constraint: Theorem 9.3 forces first-ascent feature tuples of suitable WRP maps on the family Wm,n to form a semilinear set.The proof uses bounded output growth and Presburger-definable selection, labelling, and rank-order comparisons.
Inverse-zeta behavior: The inverse zeta map sends Wm,n to paths whose first ascent has length ⌈(m+n)/(m+1)⌉.The inverse construction represents the preimage as balanced pyramids; the tallest pyramid determines the first ascent.
Conclusion: Therefore ζ−1 does not belong to WRP, despite ζ itself being WRP and semilength-preserving.This establishes that WRP-realisability under the stated convention is not preserved by inversion.

10 Machine-checked formalisation in Lean

The paper’s theory was formalised in Lean 4, with mathematical results checked from the kernel, standard axioms, and three explicitly stated admitted axioms. The formalisation also records differences between the paper’s statements and their Lean counterparts.

Formalisation: The Lean development contains roughly 82,000 lines across 162 source files and uses Lean 4 v4.33.1 with a matching Mathlib release.It contains no sorry, and the build toolchain is pinned for reproducibility.
Trust base: Every mathematical result is checked by Lean’s kernel using three standard axioms and exactly three additional admitted axioms.The development states the admitted assumptions explicitly and audits dependencies with #print axioms.
Proved and avoided results: The development proves or bypasses several literature dependencies, including semilinearity results and the counting lemma used in the structural arguments.For example, the formal proof of the relevant counting case avoids Woods’ theorem and Ehrhart theory.
WRP variants: The formalisation contains strict and relaxed WRP classes, and the negative headline theorems are restated for the paper’s stricter class.Positive memberships of ζ, H, and additive level sorts are proved directly for the strict class.
Statement differences: Several Lean closure statements are weaker or differently formulated than the paper’s versions, especially for the relaxed WRP class.The Lean statements omit some arity-preservation and case-definition claims, and subclass closure does not follow automatically from relaxed-class closure.

11 Related work and open problems

The paper situates WRP between sweep-map constructions and automata-theoretic transductions, using it to study computational resources for explicit bijections. It closes with limits of the framework and open questions about additional rank-sorting power.

Catalan bijections: No explicit semilength-preserving area–dinv bijection is known, and the paper proves that WRP cannot realise such an exchange.The related area–bounce problem remains open in full, despite a bijection on an exponentially large subset.
Automata-theoretic context: WRP isolates one global sort by unbounded additive integer ranks, extending polyregular transductions while remaining deliberately narrow.Its rank-sorting mechanism is compared with weighted MSO enumeration and lexicographic transductions, which are not equivalent classes.
Research perspective: The paper studies resources needed to compute explicit bijections between already equidistributed Catalan statistics rather than the existence of combinatorial interpretations in general.Its lower bounds constrain a mechanism for bijective proofs, not Pak-style combinatorial interpretations.
Scope boundary: Other Catalan bijections based on first-return recursion or toggle operations are outside the paper’s formalised WRP primitives and are not classified.The paper specifically mentions Deutsch’s involution and the Lalanne–Kreweras involution.
Open problems: Open problems ask whether multiple rank-sort layers form a strict hierarchy, whether WRP presentation equivalence is decidable, and which additive level sorts are polyregular.One concrete question is whether two rank-sort layers suffice for ζ−1.

Declaration of AI use

The paper reports that its mathematical theory was developed jointly by human authors and AI models, while the Lean formalisation was carried out fully by AI models.

Mathematical theory: The mathematical theory was developed jointly by the human authors and GPT Pro, Codex, and Claude.The declaration distinguishes theory development from formalisation and writing assistance.
Formalisation and writing: The Lean formalisation was carried out fully by Claude, Codex, and Aristotle.The same declaration states that Claude and Codex assisted with the paper’s writing.

A Proofs of the structural properties of WRP

The appendix proves that WRP presentations are robust under standard constructions, including restriction, case distinctions, tagged combination, concatenation, letter replacement, and reversal. These closure properties preserve bounded arity while allowing rank dimension to grow.

Restriction and cases: WRP is closed under restriction and finite definition by cases using MSO domain formulas and disjoint copy-name unions.Case presentations embed ranks into a common dimension and combine tie-orders without changing the represented outputs.
Combining outputs: WRP combines multiple outputs by tagging their letters and assigning source tags as leading atom-rank coordinates.The resulting output is tag1(T1(w)) ··· tagr(Tr(w)) on the common domain.
Concatenation: WRP supports concatenation with fixed separators by adding arity-1 separator atoms and ordering the component blocks through rank coordinates.The construction applies on nonempty inputs in the intersection of the component domains.
Letter operations: Letter replacement or deletion preserves selected atoms, ranks, tie-order, domain, and arities while changing or removing their output labels.Each selected atom contributes either the unique replacement letter or no letter when the substitution maps its label to ε.
Reversal: Output reversal is realised by negating every prefix-additive rank and reversing the MSO tie-order.The selected atoms and labels remain unchanged, while lexicographic rank order and equal-rank order are reversed.
Structural invariants: All five constructions preserve the arity bound max_j k_j, although rank dimension may increase in restriction, case, and concatenation constructions.Arity 1 remains arity 1.

A.2 Evaluation algorithms

The evaluation algorithms enumerate selected atoms in rank order without materialising the atom set. They recompute selections, labels, ranks, and comparisons from the input, yielding logarithmic space and polynomial time.

General evaluation: WRP evaluation prints one output letter at a time by repeatedly finding the least selected atom succeeding the previously emitted atom.The algorithm maintains only the last emitted atom and a best-so-far successor while scanning potential atoms.
Recomputable primitives: Potential atoms, selections, labels, ranks, and order comparisons are recomputable from the input using stored indices and finite-state scans.Rank coordinates are accumulated in O(log n)-bit counters, while order is determined by lexicographic rank comparison and the tie-order.
Space usage: O(log n) space suffices because the evaluator stores only a constant number of atoms, counters, accumulators, labels, and finite control.This avoids storing the potentially O(n^k) selected-atom collection.
Time usage: O(nk) rounds and one scan of O(nk) potential atoms per round give a polynomial-time evaluation procedure for arity at most k.The cited construction’s resource analysis states one round per output letter plus a final round.
Arity-one evaluation: For arity-one maps, forward rank accumulation is kept separate from scan direction because prefix-additive ranks are intrinsically computed left to right.The evaluator may use a reversed tie-order scan, but rank computation remains forward.

A.3 Regular nonemptiness and the logspace separation

Every WRP map has a regular language of inputs with nonempty output, but WRP is strictly weaker than deterministic logspace. The separation uses a logspace map whose nonempty-output preimage is nonregular.

Regular nonemptiness: For every WRP map T, the language of inputs in its domain with |T(w)| ≥1 is regular.Nonempty output is equivalent to selecting at least one atom, an MSO-definable condition independent of rank ordering.
Logspace witness: F≥0 copies an input exactly when no prefix has negative height and otherwise outputs ε.A single height counter and one Boolean flag suffice to decide the condition in deterministic logspace.
Strict separation: F≥0 is not WRP because its nonempty-output preimage would force the nonregular language L≥0 to be regular.The nonregularity of L≥0 follows from a pumping-lemma argument using U^pD^p.

A.4 Failure of composition closure

The appendix constructs a WRP map whose inverse image of a regular language is nonregular, proving failure of composition closure. It also shows that bounded rank sources collapse WRP to polyregularity, forcing unbounded ranks in any WRP realisation of ζ.

The separating map: The map D emits a diagnostic block, a separator, and a verbatim input block, ordered by a leading block-tag rank coordinate.The diagnostic block contains G and height-sorted B labels; the separator is #; the final block copies the input.
Diagnostic behavior: For nonempty inputs, D’s first output letter is G exactly when every prefix height is nonnegative.The sentinel G has height rank zero and precedes B-atoms tied at that rank, so it appears first precisely for inputs in L≥0.
Failure of inverse-image regularity: A regular language K of outputs beginning with G has nonregular inverse image under D.D−1(K)=L≥0 \ {ε}, which is nonregular, despite D being WRP and K being regular.
Failure of composition closure: A deterministic 2DFT S composed with D computes F≥0, so two WRP maps can have a composite outside WRP.S tests whether the first diagnostic letter is G, skips the separator, and copies the final block only when the test succeeds.
Bounded-rank collapse: If all rank sources are uniformly bounded on a WRP map’s domain, its rank comparisons become MSO-definable and the map is polyregular.Finite possible rank values permit an MSO case split that replaces rank sorting without changing the output order.
Implication for ζ: Every WRP presentation realising ζ must contain an unbounded prefix-rank source, because otherwise Theorem 4.15 would contradict ζ’s non-polyregularity.In the usual presentation, the necessary unbounded source is the height source.

B A self-contained proof of the height-sweep theorem

The section gives a self-contained proof that the height-sweep map H is a bijection on Dyck paths and exchanges the relevant peak and valley statistics, yielding Narayana symmetry.

Contour and forest encoding: The contour bijection sends a Dyck path P to an ordered plane forest with n vertices, whose leaves correspond exactly to P's peaks.The forest has one vertex per up-step and n−pk(P) internal vertices.
Contour and forest encoding: The map ψ reconstructs a Dyck word from a forest's root count and right-to-left breadth-first child counts as ψ(F)=U^r D U^{c1}D⋯D U^{cn}.The composite H=ψ∘φ is therefore the height-sweep map in the paper's conventions.
Well-definedness and bijectivity: The resulting word stays nonnegative because, before each down-step, the number of available roots and earlier children is at least the number of processed vertices.This proves that ψ maps forests into D_n.
Well-definedness and bijectivity: The leading up-run and subsequent up-runs recover the forest's root count and child-count sequence, making ψ injective.Identical breadth-first child counts reconstruct the same ordered forest, so the forests are isomorphic.
Well-definedness and bijectivity: Equal cardinalities of forests and Dyck paths make ψ, and hence H, bijective.The equality |F_n|=|D_n| turns the established injection into a bijection.
Statistic exchange: The maximal up-runs of H(P) yield pk(H(P))=n−val(P)=n−pk(P)+1 and val(H(P))=dr(P), so H exchanges val and dr.Consequently, H swaps the two exponents in the Narayana polynomial and forces N_n(q,t)=N_n(t,q).

C Proofs of the deficit-zero lemmas

These lemmas bound dinv contributions for area sequences and characterize equality cases, then construct the corresponding Dyck paths explicitly from the deficit parameters.

Deficit bounds: For each position j in an area sequence, at least one earlier entry occurs at every level below a_j, so its dinv contribution is at most (j−1)−a_j.Summing these bounds gives the deficit inequality used in Lemma 8.2.
Existence: The constructed word has a prescribed initial up-run followed by two alternating block groups, with heights controlled by the deficit parameters.The parameter bounds ensure both groups remain nonnegative, and the final down-run returns the path to zero.
Existence: The up-step starting heights of the constructed path consist of an initial staircase, b−d repeated entries at level a−1, and d entries at level a−2.This explicitly realizes the area sequence associated with the deficit parameters.
Equality characterization: Equality requires every lower level to occur exactly once before j and every other earlier entry to equal a_j or a_j+1.These two local conditions must hold at every position in a global equality case.
Equality characterization: An equality case begins with an initial staircase and then restricts all remaining entries to two adjacent levels, with their permitted order determined by the equality conditions.The full staircase is the special case with all deficit parameters zero.
Uniqueness: The relevant parameter intervals are disjoint and cover the nonnegative integers, so the deficit data uniquely determine the area sequence and the equality case is unique.The proof recovers the staircase length and top level from the parameters.