Stein’s method and the modular behavior of Eulerian numbers
Jason Fulman, Adrian Röllin · 2026
Read Stein’s method and the modular behavior of Eulerian numbers by Jason Fulman, Adrian Röllin (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-21464.txt.
Introduction
Fulman and Röllin study Eulerian numbers, which count permutations by their number of descents. Earlier work asked how evenly descent counts spread across congruence classes modulo b, a question with cryptographic motives. They give two proofs of explicit error bounds for this spread. One proof uses Stein's method with translated Poisson approximation and gives polynomial decay. The other uses Fourier analysis and gives exponential decay for fixed b, but leans on a special representation from 1973.
Catalog record
| CREATOR | Jason Fulman, Adrian Röllin |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 15450 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.21464
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Stein’s method and the modular behavior of Eulerian numbers Jason Fulman, Adrian Röllin Abstract . The Eulerian number A ( n , k ) A(n,k) counts permutations of { 1 , … , n } \{1,\dots,n\} with exactly k k descents. Motivated by problems in cryptography, several authors have studied the sum 1 n ! ∑ k ≡ j ( mod b ) A ( n , k ) \frac{1}{n!}\sum_{k\equiv j\,(\mathrm{mod}\,b)}A(n,k) and its convergence to 1 / b 1/b . We give an explicit error bound for this convergence using Stein’s method for translated Poisson approximation. 1. Introduction We say that a permutation \pi on n symbols has a descent at position i , where 1\leq i\leq n-1 , if \pi(i)>\pi(i+1) . For example, the permutation \underline{4}1\underline{5}23 has descents at positions 1 and 3 , giving a total of 2 descents. The Eulerian number A(n,k) is the number of permutations on n symbols with exactly k descents; for instance, A(3,0)=1 , A(3,1)=4 , A(3,2)=1 . We refer to Petersen 2015 for a comprehensive treatment of Eulerian numbers, and to Bayer and Diaconis 1992 , Diaconis and Fulman 2023 and Holte 1997 for their connections to card shuffling and carries in addition. For b\geq 2 and 0\leq j\leq b-1 , consider the quantity (1.1) \frac{1}{n!}\sum_{k\equiv j\ (\mathrm{mod}\ b)}A(n,k), which is the probability that the number of descents of a uniform random permutation of \{1,\dots,n\} is congruent to j modulo b . This quantity arises naturally in the cryptography literature on carries in addition; see Staffelbach and Meier 1991 , Sarkar 2009 and Alquié 2010 . For b=2 , the well known relation between Eulerian numbers and the Bernoulli numbers B_{n} gives the exact formula \frac{1}{n!}\sum_{\text{$k$ even}}A(n,k)=\frac{1}{2}\biggl(1+\frac{2^{n+1}(2^{n+1}-1)B_{n+1}}{(n+1)!}\biggr), from which it follows that the convergence to 1/2 is at rate \mathop{{}\mathrm{O}}\mathopen{}\bigl((2/\pi)^{n}\bigr) ; see Alquié 2010 . For general fixed b , Tanny 1973 proved that ( 1.1 ) converges to 1/b as n\to\infty . Tanny’s argument uses the classical fact that (1/n!)A(n,k) equals the probability that the sum of n independent \mathrm{Uniform}[0,1] random variables lies in [k,k+1) ; the convergence then follows by wrapping this sum around a circle of circumference b and applying the central limit theorem. The goal of this note is to provide an explicit error bound for this convergence. Our main result (Theorem 2.1 ) gives a bound that, unlike Tanny’s asymptotic statement, allows b to grow with n . The proof combines two ingredients: a Fourier-analytic bound on the modular behavior of the Poisson distribution (Theorem 2.2 ), and a translated Poisson approximation for the number of descents via Stein’s method of exchangeable pairs (Theorem 2.5 ). The number of descents is well known to be asymptotically normal, and a proof via Stein’s method was given by Fulman 2004 . However, since the number of descents is integer valued and we are interested in its residue modulo b , normal approximation is not directly useful; instead, we approximate by the translated Poisson distribution, which for large variances serves as a discrete analogue of the normal distribution. We apply ( Röllin 2007 , Theorem 3.1) , which provides a framework for translated Poisson approximation via exchangeable pairs, building on the exchangeable pair construction of Fulman 2004 . We refer to Ross 2011 for an introduction into Stein’s method. We conclude by noting that the cryptography papers cited above are also interested in the behavior of the i -th carry for fixed i . The discussion above concerns the i\to\infty limit, in which Eulerian numbers arise. Theorem 3.4 of Diaconis and Fulman 2009 shows that if one works base b , then slightly more than \frac{1}{2}\log_{b}(n) steps suffice for the total variation convergence of Holte’s carries Markov chain when n is large. For i this large, the probability that the i -th carry is congruent to j modulo b is therefore close to ( 1.1 ). 2. Main results Since we are working with permutations from the uniform distribution, it is equivalent to work with the random variable W(\pi) which is the number of descents of \pi^{-1} . This is equal to the number of i ( 1\leq i\leq n-1) such that i and i+1 are out of order in \pi . The following theorem is our main result. Theorem 2.1 . Suppose that n\geq 6 . Let b\geq 2 and k\in\{0,1,\dots,b-1\} . Then \biggl\lvert\frac{1}{n!}\sum_{r\equiv k\ (\mathrm{mod}\ b)}A(n,r)-\frac{1}{b}\biggr\rvert\leq\sqrt{\frac{23}{5}}\cdot\frac{1}{\sqrt{n+1}}+\frac{24}{n+1}+\frac{b-1}{b}\exp\Bigl(-\frac{n+1}{12}\bigl(1-\cos(2\pi/b)\bigr)\Bigr). The proof of the above result relies on two ingredients. The first is a bound on the modular behavior of the Poisson distribution, which is of independent interest. The second is an approximation of W by a translated Poisson distribution, which we obtain by applying Theorem 3.1 of Röllin 2007 . Theorem 2.2 . Let X\sim\mathop{\mathrm{Po}}\mathopen{}(\lambda) and let b\geq 2 . Then for any k\in\{0,1,\dots,b-1\} , \biggl\lvert\mathop{{}\mathbb{P}}\mathopen{}\bigl[X\equiv k\ (\mathrm{mod}\ b)\bigr]-\frac{1}{b}\biggr\rvert\leq\frac{1}{b}\sum_{j=1}^{b-1}\exp\bigl(-\lambda(1-\cos(2\pi j/b))\bigr)\leq\frac{b-1}{b}\exp\bigl(-\lambda(1-\cos(2\pi/b))\bigr). Proof. We use Fourier analysis on the finite abelian group \mathbb{Z}/b\mathbb{Z} . For any integer-valued random variable X and any k\in\mathbb{Z} , the indicator of the congruence class \{X\equiv k\ (\mathrm{mod}\ b)\} admits the Fourier expansion \mathop{{}\mathrm{I}}\mathopen{}\bigl[X\equiv k\ (\mathrm{mod}\ b)\bigr]=\frac{1}{b}\sum_{j=0}^{b-1}\exp\biggl(\frac{2\pi ij(X-k)}{b}\biggr). Indeed, for a fixed integer x , \frac{1}{b}\sum_{j=0}^{b-1}\exp\biggl(\frac{2\pi ij(x-k)}{b}\biggr)=\begin{cases}1,&x\equiv k\ (\mathrm{mod}\ b),\\ 0,&x\not\equiv k\ (\mathrm{mod}\ b),\end{cases} by orthogonality of characters of \mathbb{Z}/b\mathbb{Z} . Taking expectations yields \mathop{{}\mathbb{P}}\mathopen{}\bigl[X\equiv k\ (\mathrm{mod}\ b)\bigr]=\frac{1}{b}\sum_{j=0}^{b-1}\mathop{{}\mathbb{E}}\mathopen{}\bigl\{e^{{2\pi ij(X-k)}/{b}}\bigr\}. The term j=0 equals 1/b . For j\neq 0 , using the characteristic function of the Poisson distribution, \mathop{{}\mathbb{E}}\mathopen{}\bigl\{e^{2\pi ijX/b}\bigr\}=\exp\bigl(\lambda(e^{2\pi ij/b}-1)\bigr). Taking absolute values gives \bigl\lvert\mathop{{}\mathbb{E}}\mathopen{}\bigl\{e^{2\pi ij(X-k)/b}\bigr\}\bigr\rvert=\Bigl\lvert\exp\bigl(\lambda(e^{2\pi ij/b}-1)\bigr)\Bigr\rvert\,\bigl\lvert e^{2\pi ijk/b}\bigr\rvert=e^{-\lambda(1-\cos(2\pi j/b))}. Summing over j=1,\dots,b-1 yields the first inequality. The second inequality follows by bounding the sum by b-1 times its largest term. ∎ Remark 2.3 . For b=2 , the above proof gives the exact formula \biggl\lvert\mathop{{}\mathbb{P}}\mathopen{}[X\equiv k\ (\mathrm{mod}\ 2)]-\frac{1}{2}\biggr\rvert=\frac{e^{-2\lambda}}{2},\qquad k\in\{0,1\}. We proceed as in Röllin 2007 and introduce the following notion. An integer-valued random variable Y is said to have a translated Poisson distribution with parameters \mu and \sigma^{2} , written \mathop{{}\mathcal{L}}(Y)=\mathop{\mathrm{TP}}\mathopen{}(\mu,\sigma^{2}) if \mathop{{}\mathcal{L}}(Y-\mu+\sigma^{2}+\gamma)=\mathop{\mathrm{Po}}\mathopen{}(\sigma^{2}+\gamma), where \gamma=\langle\mu-\sigma^{2}\rangle denotes the fractional part of \mu-\sigma^{2} , with \langle x\rangle=x-\lfloor x\rfloor . In particular, \mathop{\mathrm{TP}}\mathopen{}(\sigma^{2},\sigma^{2})=\mathop{\mathrm{Po}}\mathopen{}(\sigma^{2}) . Approximating a random variable W by \mathop{\mathrm{TP}}\mathopen{}(\mu,\sigma^{2}) allows the mean to be matched exactly. The variance, however, can only be matched up to an additive error of at most 1 , where \sigma^{2}\leq\operatorname{Var}\mathopen{}Y=\sigma^{2}+\gamma\leq\sigma^{2}+1. This discrepancy causes no difficulty, since for the total variation distance, the resulting error is of order \mathop{{}\mathrm{O}}\mathopen{}(\sigma^{-2}) . The next goal is to approximate W(\pi) , the number of descents of the inverse of \pi , by a translated Poisson distribution. We apply the following result, which is a special case of Theorem 3.1 of Röllin 2007 . Recall that (W,W^{\prime}) is called an exchangeable pair if (W,W^{\prime}) has the same distribution as (W^{\prime},W) . We also let \mathop{d_{\mathrm{TV}}}(P,Q)=\frac{1}{2}\sum_{x\in\mathcal{X}}\lvert P(x)-Q(x)\rvert=\max_{A\subseteq\mathcal{X}}\lvert P(A)-Q(A)\rvert denote the total variation distance between probability distributions P and Q on a finite set \mathcal{X} . Theorem 2.4 (See ( Röllin 2007 , Theorem 3.1) ) . Assume that (W,W^{\prime}) is an exchangeable pair with values in the integers, such that • \mathop{{}\mathbb{E}}\mathopen{}W=\mu and \operatorname{Var}\mathopen{}W=\sigma^{2}<\infty , • \mathop{{}\mathbb{E}}\mathopen{}[W^{\prime}-\mu\mskip 0.5mu plus 0.25mu|\mskip 0.5mu plus 0.15muW]=(1-\lambda)(W-\mu) for some 0<\lambda<1 , • W^{\prime}-W\in\{-1,0,+1\} . Then, with S=S(W)=\mathop{{}\mathbb{P}}\mathopen{}[W^{\prime}=W+1\mskip 0.5mu plus 0.25mu|\mskip 0.5mu plus 0.15muW] , \mathop{d_{\mathrm{TV}}}\bigl(\mathop{{}\mathcal{L}}(W),\mathop{\mathrm{TP}}\mathopen{}(\mu,\sigma^{2})\bigr)\leq\frac{\sqrt{\operatorname{Var}\mathopen{}S}}{\lambda\sigma^{2}}+\frac{2}{\sigma^{2}}. As a consequence of Theorem 2.4 , we obtain the following result. Theorem