arxiv: 2603.21464 · v2 · submitted 2026-03-23 · 🧮 math.PR · math.CO

Recognition: 2 theorem links

· Lean Theorem

Stein's method and the modular behavior of Eulerian numbers

Jason Fulman , Adrian R\"ollin

Authors on Pith no claims yet

Pith reviewed 2026-05-15 01:20 UTC · model grok-4.3

classification 🧮 math.PR math.CO

keywords Eulerian numbersdescentsmodular distributionStein's methodFourier analysispermutationserror boundstranslated Poisson

0 comments

The pith

The proportion of permutations with descent count in any fixed residue class mod b approaches 1/b with explicit error bounds.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that for fixed b, the number of descents in a random permutation of n symbols falls into each residue class modulo b with probability approaching exactly 1/b. Explicit rates are supplied for how fast this happens: one proof uses Stein's method for translated Poisson approximation and yields polynomial decay in the error, while the other uses Fourier analysis and yields exponential decay when b is fixed. The latter proof relies on a generating-function identity from Tanny 1973 that decomposes the Eulerian numbers by residue class. A reader cares because the descent statistic appears in cryptographic constructions and in the enumeration of permutations, where knowing the modular bias with a concrete error term makes approximation reliable for large n.

Core claim

For any fixed positive integer b and any residue r mod b, the proportion of n-permutations whose descent number is congruent to r mod b equals 1/b plus an error that tends to zero as n tends to infinity. Two separate proofs deliver explicit upper bounds on this error: the Stein-method bound decays polynomially in n, while the Fourier bound decays exponentially in n for each fixed b.

What carries the argument

Stein's method for translated Poisson approximation applied to the descent statistic, together with Fourier analysis that exploits Tanny's 1973 representation of the Eulerian numbers.

If this is right

Cryptographic protocols that rely on uniform modular behavior of descents now have concrete error estimates for finite n.
The b = 2 case already known in the literature is recovered as a special case and extended to every fixed b.
Stein's method supplies a template that can be tried on other additive statistics of permutations.
Exponential decay allows reliable numerical approximation even when n is only moderately large and b is small.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Polynomial bounds from Stein's method might still be useful when b grows slowly with n, even though the paper fixes b.
The same Fourier approach could be tested on related statistics such as inversions or major index.
The error rates may inform mixing-time questions for Markov chains that generate random permutations by descent-preserving moves.

Load-bearing premise

The modular decomposition of the Eulerian numbers requires a special generating-function identity that may not hold for other permutation statistics.

What would settle it

Direct enumeration for n = 200 and b = 3 that measures the exact deviation from 1/3 and checks whether it falls below the polynomial and exponential bounds stated in the paper.

read the original abstract

The Eulerian number A(n,k) counts permutations of n symbols with exactly k descents. Motivated by problems in cryptography, several authors have studied the proportion of permutations whose number of descents lies in a fixed congruence class mod b, and its convergence to 1/b. We give two proofs of explicit error bounds for this convergence, one using Stein's method for translated Poisson approximation and one using Fourier analysis. The error bound using Fourier analysis yields exponentially decaying error bounds for fixed b, which generalises the already known case b=2; however, it makes use of a special representation due to Tanny (1973). In contrast, Stein's method only yields polynomially decaying error bounds, but we hope it has potential for generalisation beyond the present setting.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Paper supplies the first explicit polynomial and exponential error bounds for modular equidistribution of descent counts, with the exponential rate depending on Tanny's 1973 representation.

read the letter

The main thing here is explicit rates for a convergence that was already known qualitatively: the proportion of permutations with descents congruent to a fixed r mod b approaches 1/b, and the paper gives polynomial decay via Stein's method plus exponential decay via Fourier analysis for fixed b. The Stein proof applies translated Poisson approximation to the descent statistic and produces concrete polynomial bounds without extra machinery. The Fourier proof generalizes the b=2 exponential case, which is the clearest advance on the literature cited in the abstract. Both proofs are presented as complete, and the separation of methods is useful because the Stein version looks more adaptable to other permutation statistics while the Fourier one is sharper when the Tanny representation is available. The soft spot is exactly where the stress-test note flags it: the exponential bound rests on inserting Tanny's 1973 generating-function identity into the Fourier analysis, but the abstract does not show the precise step that produces the exponential factor. If that identity is only used for a closed form and the decay follows from standard estimates, the rate is robust; if it is special to this representation, the result is narrower than the headline suggests. The Stein bound is less sensitive to this issue but remains polynomial, as expected from the method. No circularity appears, the claims are consistent with the techniques named, and the work stays within standard machinery. This is for people in combinatorial probability who want quantitative control on Eulerian numbers or modular permutation statistics, including those motivated by the cryptography angle. A reader already familiar with Stein's method or Fourier analysis on discrete groups will extract the most value. It deserves a serious referee because the explicit bounds are concrete and the dual approaches give something to check and potentially build on, even if the exponential claim needs the full derivation to confirm its scope.

Referee Report

2 major / 2 minor

Summary. The paper claims to prove explicit error bounds for the convergence to 1/b of the proportion of permutations of [n] whose descent statistic lies in a fixed residue class modulo b. One proof applies Stein's method via translated Poisson approximation to obtain polynomial decay in n; the second applies Fourier analysis to the modular sum, inserting Tanny's 1973 generating-function identity to obtain exponential decay for each fixed b (generalizing the known b=2 case).

Significance. If the stated bounds hold, the work supplies the first explicit quantitative rates for this modular equidistribution problem, strengthening the qualitative 1/b limit already studied in the cryptography literature. The Stein approach is potentially extensible to other descent-like statistics, while the Fourier approach yields the stronger exponential rate; both are grounded in standard tools and avoid free parameters.

major comments (2)

[§4] §4 (Fourier analysis proof): the exponential factor in the error bound is asserted to arise after substituting Tanny's 1973 identity into the Fourier inversion formula, yet the manuscript does not exhibit the precise remainder estimate or pole-location argument that produces the exponential rate; without this step the claim that the rate is robust for fixed b cannot be verified.
[§3] §3 (Stein's method proof): the application of the translated-Poisson Stein equation to the descent indicator requires that the dependence structure induced by the descent statistic satisfies the necessary Lipschitz or bounded-difference conditions for the Stein solution; the manuscript states the bound but does not record the explicit verification of these conditions for the descent statistic.

minor comments (2)

[§2] Notation for the modular indicator function and the translated Poisson parameter should be introduced once in §2 and used consistently thereafter.
[§4] The statement of Tanny's 1973 identity is cited but not restated; including the exact generating-function formula as an equation would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading and helpful comments on our manuscript. We address each of the major comments below.

read point-by-point responses

Referee: [§4] §4 (Fourier analysis proof): the exponential factor in the error bound is asserted to arise after substituting Tanny's 1973 identity into the Fourier inversion formula, yet the manuscript does not exhibit the precise remainder estimate or pole-location argument that produces the exponential rate; without this step the claim that the rate is robust for fixed b cannot be verified.

Authors: We agree that the derivation of the exponential decay rate requires more explicit details. In the revised manuscript, we will provide the precise remainder estimate and the pole-location argument arising from substituting Tanny's 1973 identity into the Fourier inversion formula, confirming the robustness of the exponential rate for fixed b. revision: yes
Referee: [§3] §3 (Stein's method proof): the application of the translated-Poisson Stein equation to the descent indicator requires that the dependence structure induced by the descent statistic satisfies the necessary Lipschitz or bounded-difference conditions for the Stein solution; the manuscript states the bound but does not record the explicit verification of these conditions for the descent statistic.

Authors: We acknowledge that the explicit verification of the necessary conditions for the Stein solution was not included in the manuscript. We will add a detailed verification of the Lipschitz and bounded-difference conditions for the descent statistic in the revised version. revision: yes

Circularity Check

0 steps flagged

No circularity: proofs use standard Stein machinery and external Tanny citation without reduction to inputs

full rationale

The paper's derivation chain consists of two separate proofs for explicit error bounds on the modular convergence of descent statistics. Stein's method applies translated Poisson approximation directly to the descent indicator without fitting parameters to the target modular proportion or invoking self-referential quantities. The Fourier proof inserts the 1973 Tanny representation as an external generating-function identity into standard Fourier inversion estimates; this citation is independent (pre-dates the paper, externally verifiable) and does not reduce the exponential decay rate to a definition or self-citation chain. No equation equates the claimed bound to a fitted input or prior self-result by construction, so the central claims remain non-circular.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper rests on standard combinatorial facts about Eulerian numbers and generating functions plus the applicability of Stein's method to the descent statistic; no free parameters are introduced and no new entities are postulated.

axioms (2)

standard math Standard properties of the Eulerian generating function and descent statistic in the symmetric group
Invoked implicitly when applying approximation techniques to the descent count.
domain assumption Existence and form of Tanny's 1973 representation for the relevant generating function
Explicitly used in the Fourier analysis proof.

pith-pipeline@v0.9.0 · 5423 in / 1428 out tokens · 53405 ms · 2026-05-15T01:20:46.537578+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We give two proofs of explicit error bounds... one using Stein’s method for translated Poisson approximation and one using Fourier analysis... makes use of a special representation due to Tanny (1973)
IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Theorem 2.2... Fourier analysis on the finite abelian group Z/bZ... exp(−λ(1−cos(2πj/b)))

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages

[1]

Alqui´ e, D. (2010). Approximating addition by XOR: how to go all the way. IACR Cryptology ePrint archive, 2010/072

work page 2010
[2]

and Diaconis, P

Bayer, D. and Diaconis, P. (1992). Trailing the dovetail shuffle to its lair.Ann. Appl. Probab.2, 294-313

work page 1992
[3]

and Fulman, J

Diaconis, P. and Fulman, J. (2009). Carries, shuffling, and symmetric functions.Adv. in Appl. Math.43, 176-196

work page 2009
[4]

and Fulman, J

Diaconis, P. and Fulman, J. (2023).The mathematics of shuffling cards. American Math Society. 6 JASON FULMAN AND ADRIAN R ¨OLLIN

work page 2023
[5]

Fulman, J. (2004). Stein’s method and non-reversible Markov chains. InStein’s method: expository lectures and applications, IMS Lecture Notes Monograph Ser. Volume 45, 69-77

work page 2004
[6]

Holte, J. (1997). Carries, combinatorics, and an amazing matrix.Amer. Math. Monthly104, 138-149

work page 1997
[7]

(2015).Eulerian numbers

Petersen, T.K. (2015).Eulerian numbers. Birkhauser/Springer, New York

work page 2015
[8]

and Rotar, V

Rinott, Y. and Rotar, V. (1997). On coupling constructions with rates in the CLT for dependent sum- mands with applications to the antivoter model and weighted U-statistics.Ann. Appl. Probab.7, 1080-1105. R¨ ollin, A. (2007). Translated Poisson approximation using exchangeable pair couplings.Ann. Appl. Probab.17, 1596-1614

work page 1997
[9]

Ross, N. (2011). Fundamentals of Stein’s method.Probab. Surveys8, 210-293

work page 2011
[10]

Sarkar, P. (2009). On approximating addition by exclusive OR. IACR Cryptology ePrint archive, 2009/047

work page 2009
[11]

and Meier, W

Staffelbach, O. and Meier, W. (1991). Cryptographic significance of the carry for ciphers based on integer addition.Advances in Cryptology – Crypto 1990, LNCS Vol. 357, Springer, 601-614

work page 1991
[12]

Tanny, S. (1973). A probabilistic interpretation of Eulerian numbers.Duke Math. J.40, 717-722. Department of Mathematics, University of Southern California, Los Angeles, CA 90089-2532, USA Email address:fulman@usc.edu Department of Statistics and Data Science, National University of Singapore, Singapore Email address:adrian.roellin@nus.edu.sg

work page 1973