Log-concavity and related properties of the cycle index polynomials (Q1913997)

Let \(X_0 = 1\), \(X_1, X_2, \dots\) be a log-concave sequence of nonnegative real numbers (i.e., \(X^2_i \geq X_{i - 1} X_{i + 1}\) for all \(i \geq 1)\), and let \(A_n\) be the cycle index polynomial of the symmetric group of order \(n\), i.e., the \(A_n\)'s are defined by \[ \sum_{n \geq 0} A_n u^n = \exp \Bigl( \sum_{j \geq 1} X_j u^j/j \Bigr). \] Then the main theorem of this paper asserts that \(A_{n - 1} A_{n + 1} \leq A^2_n \leq {n + 1 \over n} A_{n - 1} A_{n + 1}\). This implies that the coefficients of the formal power series \(\exp (g(u))\) are log-concave whenever the coefficients of the formal power series \(g(u)\) satisfy a condition slighlty weaker than log-concavity. As corollaries, the authors are able to show log-concavity of several familiar sequences, for which it was not known previously. The proof of the first inequality is inductively and actually establishes that the difference \(A^2_n - A_{n - 1} A_{n + 1}\) can be written as a polynomial with nonnegative coefficients in the expressions \(X_j\) and \(X_j X_k - X_{j - 1} X_{k + 1}\), \(j \leq k\). The second inequality is proven combinatorially, by working with what the authors call ``marked permutations''. Finally, it is shown that the same inequalities will hold for \(n\) sufficiently large without assuming log-concavity for the \(X_j\)'s, as long as only a finite number of \(X_j\)'s is nonzero.