WorksMathematics
Log-concavity for alternating Eulerian polynomials
Abstract
Alternating Eulerian polynomials enumerate permutations by the alternating descent statistic introduced by Chebikin. We prove that their coefficient sequences are log-concave, verifying a conjecture of Lin, Ma, Wang and Wang. Our proof combines a factorization involving reciprocal quadratic factors, estimates for ordinary Eulerian zeros, and a log-concavity criterion for products of such factors. The required finite verifications use exact integer arithmetic. As applications, we obtain log-concavity for the distribution of -descents, a local limit theorem for alternating descents, and bounds for the largest coefficient. We also give a Lorentzian reformulation of the main theorem.
Introduction
Let denote the set of all permutations of . For a permutation , a descent is an index such that . As a variation of the classical descent statistic, Chebikin [5] introduced the alternating descent statistic. An index is an alternating descent of if when is odd, or when is even. Let denote the number of alternating descents of .
The alternating Eulerian polynomial is defined by
where counts permutations in with exactly alternating descents, and . The first few alternating Eulerian polynomials are , , .
A polynomial is called palindromic if for . Replacing each entry by reverses every comparison and changes the number of alternating descents from to . Consequently, is palindromic of degree ; equivalently,
Alternating Eulerian polynomials are related to tangent derivative polynomials, and their zeros lie on the unit circle [6, 12]. Lin, Ma, Wang and Wang [10] studied their sign-alternating -expansions, and Zhu [17] proved coefficientwise 2-log-convexity as the order varies. Here we study log-concavity of the coefficients for each fixed order. Further studies include type analogues and grammatical descriptions [11], combinatorial formulas and parity refinements [13, 15], and -indices [14]. Heerten, Sambale and Thäle [8] studied probabilistic limits for alternating descents.
Let be a sequence of nonnegative real numbers. The sequence is said to be unimodal if there exists an index such that . The sequence is said to be log-concave if for . For a polynomial , define
where coefficients outside the range are taken to be zero. Thus, the coefficient sequence of is log-concave if and only if for . A sequence has no internal zeros if there are no indices such that , , and . A nonnegative log-concave sequence with no internal zeros is unimodal (see, e.g., Brenti [4]).
We use two standard facts. The convolution property below follows from Brenti [4 Theorem 2.2.2 and Proposition 2.5.1]. The mixed coefficient inequality is an adjacent-index case of the inequalities of Ellard and Šmigoc [7 Theorem 2.2 and Remark 1].
Lemma 1.1 ([4 Theorem 2.2.2 and Proposition 2.5.1]). Let and be two nonzero polynomials with nonnegative log-concave coefficient sequences having no internal zeros. Then the coefficient sequence of is also nonnegative, log-concave, and has no internal zeros.
Lemma 1.2 ([7 Theorem 2.2 and Remark 1]). Let
Then
where coefficients outside the range of are taken to be zero.
Since , factoring the quadratics into linear factors with constant term 1 gives a self-conjugate list of parameters in the closed right half-plane. The coefficients are the corresponding elementary symmetric functions, so (1.2) follows from the adjacent-index inequalities in the cited results.
Lin, Ma, Wang and Wang [10 Theorem 1.1 and Conjecture 5.1] proved the unimodality of the alternating Eulerian polynomials and conjectured that their coefficient sequences are log-concave for all . We prove this conjecture in the following theorem.
Theorem 1.3. For every , the coefficient sequence of the alternating Eulerian polynomial is log-concave.
The rest of this paper is organized as follows. In Section 2, we establish the factorization of alternating Eulerian polynomials and a lower bound for the number of factors with parameters exceeding . In Section 3, we prove an endpoint reduction criterion and a smoothing lemma. In Section 4, we establish a block criterion and complete the proof of Theorem 1.3. Finally, Section 5 gives applications to the distribution of 3-descents and local limits, bounds for the largest coefficient, and a Lorentzian reformulation of the main theorem.
Factorization and strong-factor estimates
The reciprocal-quadratic factorization follows from the zero results of Ma and Yeh [12]. We identify its parameters in terms of ordinary Eulerian zeros, which allows us to estimate the number of strong factors needed for the block criterion in § 4.
Let
be the ordinary Eulerian polynomial, where denotes the number of descents. It is well known that all zeros of are simple and negative for ; see [6]. The complement map also gives the palindromic identity
Hence the roots other than occur in reciprocal pairs, with one root less than and the other in . The root occurs precisely when is even. We now use these properties to obtain a factorization of the alternating Eulerian polynomials.
Proposition 2.1. For , let . There exist distinct numbers such that and
where .
Proof. The cases follow from and . Suppose that . Let be the tangent derivative polynomial, defined by
Ma and Yeh [12] established the identity
We first relate the roots of to those of the ordinary Eulerian polynomial . By the classical Eulerian generating-function identity [16 Proposition 1.4.4], after normalization, we have,
Consider a pair of reciprocal roots and of , where , and put . Since , the chain rule gives
Moreover, since , substituting into (6) yields
Thus implies .
For the reciprocal root , the corresponding value is . Applying the same identity with replaced by gives .
Next, solving gives . Since , we have . Consequently,
As , equation (5) implies that
The same argument applied to shows that .
For each reciprocal pair, write with . The corresponding roots and satisfy , . Furthermore,
Therefore, the corresponding quadratic factor is
When is even, the additional root of corresponds to . Since for even , equation (5) gives . This contributes the factor .
Since has distinct negative roots and the transformations above are injective, we have obtained all roots of . Comparing constant terms gives (4). Finally, implies , completing the proof.
A quadratic factor in (4) is called strong if . Since is decreasing for , we estimate the number of strong factors by counting the zeros of in a suitable interval.
Lemma 2.2. For , at least of the quadratic factors in (4) are strong.
Proof. We count zeros of in and then show that every such zero gives .
Step 1. Expressing the Eulerian polynomial as a sum over poles. Logarithmically differentiating the classical product
and using the identity give
The paired terms equal
The series and its derivatives of every positive order converge locally uniformly on the real axis. Thus, termwise differentiation is justified. Define
Differentiating (2.6) times gives
On the other hand, substituting into (2.4) yields
Comparing these two identities, we obtain
Since the factor multiplying is nonzero for real , the two functions and have the same real zeros.
Step 2. Estimating the contribution of the remaining poles. For , let . The two terms in corresponding to give
Consequently,
Since and ,
As , we have
Therefore,
In particular, whenever , the function has the same sign as the cosine.
Step 3. Counting the zeros by alternating signs. The function is continuous and strictly decreasing on . Hence runs through the interval
We claim that this interval has length greater than . Using and for , we obtain
Thus the interval (11) contains at least consecutive integers. For each such integer , there is a unique satisfying . At these points,
By (10), the corresponding values of are nonzero and alternate in sign. The intermediate value theorem therefore gives a zero of between each pair of consecutive points. These zeros are distinct and lie in . Hence has at least
distinct zeros in . By (9), the same holds for .
Step 4. Obtaining strong factors. It remains to show that every zero counted above corresponds to a strong factor. Using the Taylor series for and bounding its terms from onward by a geometric series, we obtain
Thus . Since is strictly decreasing for , every zero satisfies
By Proposition 2.1, distinct positive zeros correspond to distinct quadratic factors. Therefore at least factors are strong, as required. This proves the lemma.
Log-concavity under parameter variation
To apply the strong-factor estimate from Section 2, we establish two tools for products of reciprocal quadratic factors.
Let with for or . For each , the identity
gives
where . By Lemma 1.2, whenever is a product of factors with . The preceding identity leads to the following endpoint reduction criterion for log-concavity.
Proposition 3.1. Let and for . For each fixed integer , the minimum of
over is attained when for all . Consequently, the coefficient sequence of the product is log-concave for all if and only if it is log-concave whenever for all .
Proof. The case is immediate. Fix and all parameters except , and let
By (3.1), we have . Since by Lemma 1.2, we consider two cases.
If , then
for . Thus the minimum on is attained at .
If , then (3.1) is a concave quadratic in . Its minimum on is therefore attained at an endpoint.
Thus, for fixed values of the other parameters, the minimum with respect to is attained at one of the endpoints of .
Since the expression is continuous on the compact parameter box, it attains a global minimum. Starting from a minimizer, we can successively replace each parameter by a suitable endpoint without increasing the value. After all parameters have been replaced, we obtain a vertex at which the global minimum is attained.
Consequently, if the coefficient sequence of the product is log-concave at every vertex, then throughout the box for every relevant . The converse is immediate.
Suppose that the coefficient sequence of is nonnegative, log-concave, and has no internal zeros. Then
If , the inequality is immediate. Otherwise, the absence of internal zeros implies that . Multiplying the two log-concavity inequalities
and dividing by gives (3.2). Applying this inequality at and gives , as defined in (3.1).
The following lemma allows us to replace factors by while preserving log-concavity under suitable assumptions.
Lemma 3.2. Let be a nonzero polynomial with nonnegative coefficients and no internal zeros, and let be a nonnegative integer. Suppose that the coefficient sequence of
is log-concave for every . Then, for every integer and , the coefficient sequence of
is log-concave.
Proof. First, suppose that has nonnegative, log-concave coefficients and no internal zeros, and that also has a log-concave coefficient sequence. By (3.1),
All three terms on the right are nonnegative for , since by (3.2). Consequently,
has a log-concave coefficient sequence for every .
If , the conclusion follows directly from the hypothesis. We assume for the remainder of the proof that . Since has a log-concave coefficient sequence, cannot be a monomial. Indeed, if with , then , a contradiction. Thus the support of contains at least two consecutive indices. Multiplication by , where , preserves this property and introduces no internal zeros. Hence all products considered below have nonnegative coefficients and no internal zeros.
We prove by induction on that
has a log-concave coefficient sequence whenever and .
For , the assertion follows from the hypothesis of the lemma. Suppose that it holds for , and fix with .
Since , , the induction hypothesis shows that both
and
have log-concave coefficient sequences. Moreover, the first product has nonnegative coefficients and no internal zeros, as established above. Since the second product is the first multiplied by , applying (3.3) with shows that
has a log-concave coefficient sequence. This completes the induction. Taking and gives the desired conclusion.
Proof of Theorem 1.3
We first establish a block criterion for log-concavity and then combine it with Lemma 2.2 to prove Theorem 1.3.
Proposition 4.1. For integers and , let
Then
Equality holds only when .
Proof. Each factor in (4.1) is palindromic, so is palindromic of degree and . Thus the inequalities in (4.2) imply log-concavity of the entire coefficient sequence.
We verify these inequalities as follows.
For each , we first compute the coefficients of by multiplying its eight quadratic factors. The coefficients of are then obtained recursively from
Using these coefficients, we evaluate for .
The verification involves integer comparisons. All the computed values are nonnegative, with equality occurring only at .
The accompanying script verify_log_concavity.py, available in the GitHub repository, reproduces this verification using exact integer arithmetic. This completes the proof.
We now combine Proposition 4.1 with the results of § 3 to obtain the following block criterion.
Proposition 4.2. Suppose , with , and . Then the coefficient sequence of the polynomial
is log-concave.
Proof. Let . We first show that has a log-concave coefficient sequence for every integer . Fix such an . By Proposition 3.1, it suffices to consider for , with the remaining parameters fixed at zero. If exactly of the eight parameters equal , the corresponding product is
By Proposition 4.1 and the palindromicity of , its coefficient sequence is log-concave for every . Since multiplication by a positive constant preserves log-concavity, the same holds for . Proposition 3.1 therefore shows that has a log-concave coefficient sequence for all .
Moreover, has positive coefficients and hence has no internal zeros. Thus all the hypotheses of Lemma 3.2 are satisfied with . It follows that
has a log-concave coefficient sequence for every and , as required.
Remark 4.3. The bound in Proposition 4.2 is sharp. Taking for and for gives
Its first three coefficients are , , and , respectively. Hence the log-concavity difference at index is , which is negative when . Thus the bound cannot be improved.
We now complete the proof of Theorem 1.3 using exact integer verification for and the strong-factor estimate together with the block criterion for .
Proof of Theorem 1.3. Case 1. . We use the recurrence of Lin, Ma, Wang and Wang [10 Theorem 2.1]:
where unless . Starting from , this recurrence determines the coefficients of for every .
By (1), we have . Thus it suffices to verify for . The number of required comparisons is . An exact integer computation using (22) shows that all these differences are nonnegative, with equality only at . The accompanying script verify_log_concavity.py reproduces this verification. Hence the theorem holds for .
Case 2. . Let . By Proposition 2.1, we have
where and .
Let . Since , we have . By Lemma 2.2, the number of strong factors is at least
Moreover, the definition of gives , and hence
where the last inequality follows from .
We can therefore choose strong factors and divide them into groups, each containing eight strong factors. By (24), the number of remaining factors satisfies
These factors can be distributed among the groups so that each group contains at most 73 additional factors.
The eight strong factors in each group have parameters in , while all remaining parameters are nonnegative. Thus, by Proposition 4.2, every group has a log-concave coefficient sequence. Since all the factors have positive coefficients, each group also has no internal zeros. Applying Lemma 1.1 repeatedly, we conclude that
has a log-concave coefficient sequence with no internal zeros.
Finally, . Since the coefficient sequence of is log-concave, another application of Lemma 1.1 shows that multiplying by the possible factor preserves log-concavity. Multiplication by also preserves log-concavity. Therefore, the coefficient sequence of is log-concave for all , which completes the proof.
As a consequence of Theorem 1.3, we recover the unimodality established by Lin, Ma, Wang and Wang [10].
Corollary 4.4. For every , the coefficient sequence of is unimodal.
Applications
We give four consequences of Theorem 1.3. We first transfer log-concavity to the distribution of 3-descents and derive a local limit theorem. We then bound the largest coefficient and obtain a Lorentzian reformulation of the main theorem.
For , let denote the number of indices for which the consecutive triple has relative order 132, 213 or 321. Chebikin’s equidistribution theorem [5 Theorem 2.3 and Corollary 2.2] relates this statistic to alternating descents.
Corollary 5.1. For every ,
Consequently, the coefficient sequence on the left is log-concave for every .
Normal approximation for alternating descents was studied by Heerten, Sambale and Thäle [8]. Theorem 1.3 supplies the log-concavity hypothesis in Bender’s local limit theorem [1]. We give the resulting coefficient estimate below.
Corollary 5.2. As ,
where outside . Consequently,
Proof. Hwang, Chern and Duh [9 Section 5.4.2] established asymptotic normality with centering and scale . The centering may be replaced by , since the difference divided by tends to zero. By Proposition 2.1, the coefficients are positive, and by Theorem 1.3, they form a log-concave sequence. Since , Bender’s local limit theorem [1] gives (5.2).
Taking in (5.2), the exponential term tends to 1, giving (5.3).
The main theorem also yields bounds for the largest coefficient through a concentration inequality for symmetric log-concave distributions.
Corollary 5.3. For every , the maximum coefficient of is , and
Proof. Palindromicity and Corollary 4.4 show that the central coefficient is a maximum coefficient. Let be the number of alternating descents in a uniformly random permutation in . Then .
Each alternating descent indicator has variance . Two adjacent indicators are simultaneously with probability , so their covariance is ; nonadjacent indicators are independent. Hence
By Theorem 1.3 and Proposition 2.1, the distribution of is log-concave with no internal zeros, and palindromicity makes it symmetric about . Thus Bobkov, Marsiglietti and Melbourne [2 Theorem 1.1] give
Substituting the variance above and multiplying by gives (5.4). □
We finish with a reformulation of Theorem 1.3 using the characterization of bivariate Lorentzian polynomials.
Corollary 5.4. For every , the homogeneous polynomial
is Lorentzian and completely log-concave.
Proof. The cases are immediate. For , the bivariate characterization in [3 Example 2.26] reduces the Lorentzian property to log-concavity and the absence of internal zeros of the coefficients after division by . For (5.5), these normalized coefficients are exactly . They are positive by Proposition 2.1 and log-concave by Theorem 1.3. Complete log-concavity follows from [3 Theorem 2.30]. □
Conflict of Interest
The authors declare no conflict of interest.
Acknowledgements
This work was supported in part by the National Natural Science Foundation of China (Grant Nos. 12271078, 12101110) and the Scientific Research Fund of Liaoning Provincial Education Department (Grant No. LJ212410173071).
References
- [1]E.A. Bender, Central and local limit theorems applied to asymptotic enumeration, J. Combin. Theory Ser. A 15(1) (1973) 91–111.DOI
- [2]S.G. Bobkov, A. Marsiglietti, J. Melbourne, Concentration functions and entropy bounds for discrete log-concave distributions, Combin. Probab. Comput. 31(1) (2022) 54–72.arxiv.org/abs/2007.11030
- [3]P. Brändén, J. Huh, Lorentzian polynomials, Ann. of Math. (2) 192(3) (2020) 821–891.arxiv.org/abs/1902.03719
- [4]F. Brenti, Unimodal, log-concave and Pólya frequency sequences in combinatorics, Mem. Amer. Math. Soc. 81 (1989) no. 413.DOI
- [5]D. Chebikin, Variations on descents and inversions in permutations, Electron. J. Combin. 15(1) (2008) Paper No. R132.arxiv.org/abs/0804.1935
- [6]C.O. Chow, New proofs of interlacing of zeros of Eulerian polynomials. III, Enumer. Combin. Appl. 4(2) (2024) Paper No. S2R14.DOI
- [7]R. Ellard, H. Šmigoc, Families of Newton-like inequalities for sets of self-conjugate complex numbers, Linear Algebra Appl. 597 (2020) 46–68.arxiv.org/abs/1604.05148
- [8]N. Heerten, H. Sambale, C. Thäle, Probabilistic limit theorems induced by the zeros of polynomials, Math. Nachr. 297(5) (2024) 1772–1792.arxiv.org/abs/2207.08469
- [9]H.-K. Hwang, H.-H. Chern, G.-H. Duh, An asymptotic distribution theory for Eulerian recurrences with applications, Adv. in Appl. Math. 112 (2020) Paper No. 101960.arxiv.org/abs/1807.01412
- [10]Z. Lin, S.-M. Ma, D.G.L. Wang, L. Wang, Positivity and divisibility of enumerators of alternating descents, Ramanujan J. 58(1) (2022) 203–228.DOI
- [11]S.-M. Ma, Q. Fang, T. Mansour, Y.-N. Yeh, Alternating Eulerian polynomials and left peak polynomials, Discrete Math. 345(3) (2022) Paper No. 112714.arxiv.org/abs/2104.09374
- [12]S.-M. Ma, Y.-N. Yeh, Enumeration of permutations by number of alternating descents, Discrete Math. 339(4) (2016) 1362–1367.DOI
- [13]Q. Pan, A new combinatorial formula for alternating descent polynomials, preprint (2022), arXiv:2207.06212.arxiv.org/abs/2207.06212
- [14]Q. Pan, C. Qian, On the $cd$-index for alternating descents, Electron. J. Combin. 31(4) (2024) Paper No. P4.29.DOI
- [15]Q. Pan, J. Zeng, Enumeration of permutations by the parity of descent positions, Discrete Math. 346(10) (2023) Paper No. 113575.arxiv.org/abs/2209.15302
- [16]R.P. Stanley, Enumerative Combinatorics, Vol. 1, 2nd ed., Cambridge University Press, Cambridge, 2012.
- [17]B.-X. Zhu, Positivity of iterated sequences of polynomials, SIAM J. Discrete Math. 32(3) (2018) 1993–2010.arxiv.org/abs/1807.01062