The Range of The Des Statistic for Conjugacy Classes in S n

Yisca Kares · 2025

Read The Range of The Des Statistic for Conjugacy Classes in S n by Yisca Kares (2025) 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-2505-22828.txt.

Introduction

Yisca Kares studies a counting measure on rearrangements in a 2025 mathematics paper. The setting is the symmetric group, the set of all ways to shuffle a fixed list of items. Items are grouped into conjugacy classes by their cycle shape. The measure, called the des statistic, counts falls in a rearrangement when read in order.

Kares pins down the full range of that measure inside every class. The lowest value is one for every class except the identity, where nothing moves. Every value between that floor and the top of the range really occurs, with no gaps. The paper also gives a hands-on method to build a rearrangement hitting any chosen value, and draws out what the result means for counting problems.

Catalog record

CREATORYisca Kares
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE28 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-22828

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

The Range of The Des Statistic for Conjugacy Classes in S n S_{n} Thanks: Department of Applied Mathematics, Jerusalem College of Technology, Jerusalem, Israel Michlalah-Jerusalem College, Department of Mathematics, Jerusalem, Israel Department of Mathematics, Open University, Ra’anana, Israel Yisca Kares Abstract . We determine the range of the des statistic on every conjugacy class in the symmetric group S n S_{n} , prove that the minimum is 1 1 (except for the identity class), and show that every intermediate value from 1 1 to the maximum value is attained. We also demonstrate a constructive method to achieve every value in the range and discuss its combinatorial implications. 1. Introduction Let S_{n} be the symmetric group on n elements, and let \pi=[\pi(1)\pi(2)...\pi(n)] be a permutation in S_{n} . We say that i\in\{1,\dots,n-1\} is a descent of a permutation \pi\in S_{n} if \pi(i)>\pi(i+1) . Denote Des(\pi) the set of the descents of \pi and des(\pi)=|Des(\pi)| as the number of the descent of \pi . The des statistic discussed in this work has been extensively studied on the entire symmetric group. Our goal is to restrict attention to individual conjugacy classes and analyze more closely the behavior of the statistic within them, determining both the minimum value and the full range of attained values. One of the first to define and study this permutation statistic was Euler. The distribution function of the des statistic, denoted A_{n}(q) , is known as the Eulerian p olynomial and is defined via the generating function \sum_{n\geq 0}A_{n}(q)\frac{x^{n}}{n!}=\frac{q-1}{q-e^{(q-1)x}}. Stieltjes [ 11 ] established a connection between Eulerian polynomials and continued fractions, given by: \sum_{n\geq 0}A_{n}(q)z^{n}=\frac{1}{1-\frac{z}{1-\frac{qz}{1-\frac{2z}{1-\frac{2qz}{1-\cdots}}}}}. Another property associated with Eulerian polynomials is the property due to Rolle [ 1 ] , which states that all roots of the Eulerian polynomial are real, negative, and pairwise distinct. Euler also introduced the Eulerian numbers A_{n,k} , defined as follows: A_{n,k}:=|\{\pi\in S_{n}\mid\text{des}(\pi)=k\}| Euler [ 5 ] showed that A_{n}(q)=\sum_{k\geq 0}A_{n,k}q^{k} . Alternatively, using the recurrence relation A_{n,k}=(n-k)A_{n-1,k-1}+(k+1)A_{n-1,k} , shown in [ 10 ] , one can derive the identity A_{n}(q)=\sum_{k\geq 0}A_{n,k}q^{k} . From this, it follows that for all n,k with 0\leq k\leq n , we have 0<A_{n,k} . Thus, for all n,k , the coefficient of q^{k} in the Eulerian polynomial A_{n}(q) is positive. This ensures that every value 0\leq k\leq n appears as the descent number of some permutation in S_{n} . This property guarantees that all values between minimum and maximum are realized, is the continuity property of the des statistic in the symmetric group S_{n} . Cellini [ 3 ] derived an explicit formula for the Eulerian numbers. The distributions of statistics on fixed conjugacy classes of S_{n} are known exactly for some classical statistics: Gessel and Reutenauer [ 7 ] derived a generating function for the joint distribution of descents and the major index over the conjugacy class. Brenti [ 2 ] provided a generating function for the excedance statistic on conjugacy classes in terms of Eulerian polynomials. Several asymptotic results have been established. Fulman [ 6 ] proved that the distributions of descents and the major index converge to a normal distribution in conjugacy classes with sufficiently large cycles. Kim and Lee [ 8 ] later extended this result to all conjugacy class of S_{n} . Loth, Levet, Liu, Stucky, Sundaram, and Yin [ 9 ] studied the expectations of various permutation statistics, treating them as random variables. The paper is organized as follows: Section 2 establishes the minimal value attained in each conjugacy class. In Section 3, we prove that in every conjugacy class, except for the class of \pi=e , each value from 1 to the maximum value of the des statistic in that class is attained. If {C}_{n}=\{e\} , the result holds trivially, since \{\des(\pi)|\pi\in{C}_{n}\}=\{0\} . Therefore, throughout the proofs, we assume that {C}_{n}\neq\{e\} . 2. Minimum value In this section, we establish the following result. Theorem 2.1 . Let {C}_{n}\neq\{e\} be a conjugacy class in the symmetric group S_{n} . Then \min_{\pi\in C_{n}}des(\pi)=1 Definition 2.2 . Let n\in\mathbb{N} , and let \lambda=(a_{1},...,a_{t})\vdash n , that is, \lambda is a partition of n , i.e., a_{1}+...+a_{t}=n and 0<a_{i+1}\leq a_{i} for all i\in[1,t-1] . The Young diagram Y_{\lambda} corresponding to the partition \lambda , consists of n cells in the plane, arranged in left-justified rows, where the i -th row has a_{i} cells. proof of theorem 2.1 . The identity permutation e admits a singleton conjugacy class, and it is the only permutation with des(\pi)=0 . We consider conjugacy classes {C}_{n}\neq\{e\} . Let C_{n}\neq\{e\} . We now show that there exists a permutation \tau\in C_{n} such that des(\tau)=1 . Conjugacy classes in {S}_{n} are determined by their cycle structures, which are partitions of n. Let (a_{1},...,a_{k}) be the cycle structure of {C}_{n} such that 0<a_{i+1}\leq a_{i} for all 1\leq i<k . Let {Y}_{\lambda} be the Young diagram corresponding to the cycle structure \lambda=(a_{1},...,a_{k})\vdash n . We fill the boxes of the diagram as follows: the numbers 1,...,n will be filled from the leftmost column to the rightmost column, with each column filled from bottom to top in order. We now write each row in this diagram as a cycle, and let \tau^{-1} be the permutation formed by composing these cycles in reverse order. We claim that des(\tau)=1 : By the construction, we observe that for all 1\leq i\leq n if i does not appear in the first column or the first row of the diagram, then \tau(i)<\tau(i+1) . The value {k} , which is the number of cycles in \tau , appears in the first position in the first column (see example 2.3 below). For every {i}\neq{k} appearing in the first column, the value \tau(i+1) appears in the row above the value \tau(i) , and in the same column or to the right. Therefore, in this case also, \tau(i)<\tau(i+1) . For every {i}\neq{k} appearing in the first row, the value \tau(i+1) is in a column to the right of the value \tau(i) , so again \tau(i)<\tau(i+1) . Because {C}_{n}\neq{e} , the Young diagram has at least two columns, i.e., {k}<{n} hence we get \tau(k)=n>\tau(k+1) . Therefore, des(\tau)=1 , and so \min_{\pi\in C}des(\pi)=1 . ∎ Example 2.3 . let {C}_{n} with a cycle structure (4,4,3)\vdash 11 . The filled diagram will be as follows {3} {11} {2} {10} {1} {7} \Longrightarrow \tau^{-1}=(3,6,9,11)(2,5,8,10)(1,4,7) Hence, the resulting permutation is \tau=(7,4,1)(10,8,5,2)(11,9,6,3) . Let us now recall a result dealing with the number of permutations with minimal des value in the conjugacy class of large cycles: Towards the end of the paper of Crochemore-Désarménien-Perrin [ 4 ] , the authors conclude, utilizing the work of Gessel-Reutenauer, that for the conjugacy class of large cycle of length n , denoted by C(n) , the number of permutations with minimal des value is equal to the number of primitive binary words of length n , known as Lyndon words. Explicitly, we have \#\{\pi\in C(n)|~des(\pi)=1\}=L_{n}=\frac{1}{n}\sum_{d|n}\mu\left(\frac{n}{d}\right)2^{d} , where \mu is the Möbius function. Theorem 2.1 shows that the value L_{n} is positive. 3. Continuity of the des statistic We now prove that for each conjugacy class {C}_{n} , every value from 1 to the maximum value is attained. Definition 3.1 . Let {S}_{n} be the symmetric group and let 1\leq i\leq n-1

Read the complete text