REVIEW
The counts of parity-odd vs even late-growing permutations in the group $\mathbb{S}_{2p-1}$ differ by $(-1)^p$
Combinatorics · Submitted 26 Oct 2026 · 13 references
Pith's verdict: The parity pattern that was empirical in their earlier preprints is now a proved theorem, with a clean two-involution proof that I checked and found sound.
Why Pith says this
Highlight any text to comment on it.
Referee report
The paper
The paper claims
The paper proves that parity-even and parity-odd late-growing permutations of $2p-1$ objects differ in count by exactly one, with the majority side alternating with $p$.
The reading
What carries the argument
The carrying device is the walk encoding. Reading a contributing permutation $\sigma$ from right to left, dropping the first entry, and shifting every remaining entry down by $p+1$ yields an ordering $\tau$ of the symmetric increment set $V_p = \{-(p-1), \ldots, -1, 0, 1, \ldots, p-1\}$; the running sum $T_k = \tau_1 + \cdots + \tau_k$ is the walk's height, and the permutation is late-growing exactly when every height stays in $\mathbb{Z}_{\geq 0}$. On these legal walks the paper defines two parity-reversing involutions: Move 1 exchanges the two entries of the earliest 'free' neighbouring pair — free meaning the walk can afford to take the second entry first — and a lemma shows the set of free pairs is unchanged by such exchanges; Move 2 acts on 'rigid' walks, which a structural proposition pins to the shape $(0, x_1, y_1, \ldots, x_m, y_m)$ with positive payments $x_i$ and negative debts $y_i$ in some order, exchanging two debts under the largest payment when the inequalities of Lemma 4.2 hold. A locked-tail lemma ensures the moves cover everything except the staircase increments $\tau^* = (0, 1, -1, 2, -2, \ldots, m, -m)$, whose parent permutation $\sigma^*$ is the single survivor and the source of the sign.
Extended reading notes
Core claim
On the paper's own terms, the central claim is the identity $\sum_{\sigma \in \Phi_p} (-1)^\sigma = (-1)^{p+1}$ for the set $\Phi_p \subseteq \mathbb{S}_{2p-1}$ of late-growing permutations, so $|\Phi_p^+| - |\Phi_p^-| = (-1)^{p+1}$: even permutations outnumber odd ones by one when $p$ is odd, odd outnumber even when $p$ is even, and $|\Phi_p|$ is odd for every $p$. The proof is a cancellation argument: every late-growing permutation except the staircase $\sigma^* = (1, 2, 2p, 3, 2p-1, \ldots, p, p+2, p+1)$ is paired with an opposite-parity partner by one of two involution moves on the walk encoding, and the sign of the survivor is computed directly as $(-1)^{\sigma^*} = (-1)^{(p-1)^2} = (-1)^{p+1}$. The paper also records that the number of rigid, Move-1-immune permutations stays proportionally tiny ($1$, $1$, $3$, $15$, $121$, $1329$ for $p = 1, \ldots, 6$ among totals surpassing $10^6$ at $p = 6$), and it reports a verified-for-$p \leq 14$ phenomenon in which partial sums over subsets with a pinned zero height reproduce the Wronskian constants $c(p)$ up to sign.
Load-bearing premise
The load-bearing premise is exact equivalence between the late-growing partial-sum condition and the walk condition that the shifted right-to-left increments never drive the height below zero; both pairing moves and both structural lemmas live inside that encoding, so if the equivalence failed for even one permutation, the involution would be partitioning the wrong set.
Editorial extensions
If this is right
- The set $\Phi_p$ of late-growing permutations of $2p-1$ objects has odd cardinality for every $p \geq 1$, since it splits into opposite-parity pairs plus the staircase permutation.
- The signed sum $\sum_{\sigma \in \Phi_p} (-1)^\sigma$ equals $(-1)^{p+1}$, so the dominant parity subset flips at every increment of $p$; this is verified computationally through $p = 14$ and now proved for all $p$.
- Only the staircase permutation survives the pairing, so the parity imbalance of the whole family $\Phi_p$ is determined by the single permutation $\sigma^*$ with monotonically growing step amplitudes.
- Proposition 6.1 (checked for $p \leq 14$) shows that summing the signed Wronskian contributions only over permutations with a pinned zero height at a fixed step reproduces the full constant $c(p)$ up to sign, and Conjecture 6.2 predicts a sign pattern of period 4 in the step and period 2 in $p$.
- The strict positivity and rapid growth of the constants $c(p)$ coexist with the near-perfect parity balance of $\Phi_p$, so the sign of the Wronskian accumulation is a separate phenomenon from the parity distribution; the paper leaves the nature of that hidden asymmetry as future work.
Reading between the lines
- Editorially extending the paper: the two moves are defined purely on shifted increments, so the parity theorem does not actually need the Wronskian origin; the same pairing could be restated as an elementary proof about partial sums alone, making the result self-contained for a purely combinatorial reader.
- A testable extension the authors do not pursue: run the free-pair/rigid dichotomy on the even-object counts the paper notes behave visibly differently; if an analogue of the staircase exists there, its sign would quantify the parity imbalance of that family as well.
- The period-4-in-$k$, period-2-in-$p$ sign pattern of Conjecture 6.2 suggests that the choice of pinning step $k$ for fast evaluation of $c(p)$ could follow a simple modular rule; pushing the verification beyond $p = 14$ is a direct computational check of this.
Original abstract
A permutation $\sigma\in\mathbb{S}_n$ of objects $\{1,\ldots,n\}$ is called \emph{late-growing} if its partial sums never exceed the respective partial sums of the `average' permutation (with the arithmetic mean $n^{-1}\cdot\sum_{i=1}^n i = (n+1)/2$ of $1,\ldots,n$ on average at each entry $\sigma(i)$): $\sum_{i=1}^k \sigma(i) \leqslant k\cdot (n+1)/2$ for all positive $k\leqslant n$. We prove that for $n=2p-1$ odd, the set $\Phi_p\subseteq \mathbb{S}_{2p-1}$ of late-growing permutations is partitioned into parity-even vs odd elements, $\Phi_p = \Phi_p^{+} \sqcup \Phi_p^{-}$, in an almost symmetric way: $| \Phi_p^{+} | - | \Phi_p^{-} | = (-1)^{p+1}$. The proof is constructive: by viewing the permutations $\sigma\in\Phi_p$ as constrained walks on the integral lattice $\mathbb{Z}$, we describe two filters that pair all but one element in $\Phi_p^{+}$ versus $\Phi_p^{-}$; the remaining walk $\sigma^*$ with monotonically growing step amplitudes determines the dominant parity subset.
The compiled record
The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
The abstract, sentence by sentence
A permutation $\sigma\in\mathbb{S}_n$ of objects $\{1,\ldots,n\}$ is called \emph{late-growing} if its partial sums never exceed the respective partial sums of the `average' permutation (with the arithmetic mean $n^{-1}\cdot\sum_{i=1}^n i = (n+1)/2$ of $1,\ldots,n$ on average at each entry $\sigma(i)$): $\sum_{i=1}^k \sigma(i) \leqslant k\cdot (n+1)/2$ for all positive $k\leqslant n$. We prove that for $n=2p-1$ odd, the set $\Phi_p\subseteq \mathbb{S}_{2p-1}$ of late-growing permutations is partitioned into parity-even vs odd elements, $\Phi_p = \Phi_p^{+} \sqcup \Phi_p^{-}$, in an almost symmetric way: $| \Phi_p^{+} | - | \Phi_p^{-} | = (-1)^{p+1}$. The proof is constructive: by viewing the permutations $\sigma\in\Phi_p$ as constrained walks on the integral lattice $\mathbb{Z}$, we describe two filters that pair all but one element in $\Phi_p^{+}$ versus $\Phi_p^{-}$; the remaining walk $\sigma^*$ with monotonically growing step amplitudes determines the dominant parity subset.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | A permutation $\sigma\in\mathbb{S}_n$ of objects $\{1,\ldots,n\}$ is called \emph{late-growing} if its partial sums never exceed the respective partial sums of the `average' permutation (with the arithmetic mean $n^{-1}\cdot\sum_{i=1}^n i = (n+1)/2$ of $1,\ldots,n$ on average at each entry $\sigma(i)$): $\sum_{i=1}^k \sigma(i) \leqslant k\cdot (n+1)/2$ for all positive $k\leqslant n$. | background 1.00 | 0.12 | 0.02 | asserted 0.98 |
| s1 | We prove that for $n=2p-1$ odd, the set $\Phi_p\subseteq \mathbb{S}_{2p-1}$ of late-growing permutations is partitioned into parity-even vs odd elements, $\Phi_p = \Phi_p^{+} \sqcup \Phi_p^{-}$, in an almost symmetric way: $| \Phi_p^{+} | - | \Phi_p^{-} | = (-1)^{p+1}$. | result 1.00 | 0.96 | 0.94 | asserted 1.00 |
| s2 | The proof is constructive: by viewing the permutations $\sigma\in\Phi_p$ as constrained walks on the integral lattice $\mathbb{Z}$, we describe two filters that pair all but one element in $\Phi_p^{+}$ versus $\Phi_p^{-}$; the remaining walk $\sigma^*$ with monotonically growing step amplitudes determines the dominant parity subset. | method 0.98 | 0.95 | 0.08 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
Figures
Figures reproduced from arXiv:2610.35779 by the authors.
References
Discussion
Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.