A theorem of log-concavity or inequalities for elementary symmetric polynomials

Philippe Pitteloud


September 27,
refreshments at 3:45pm


Many integer sequences arising from combinatorics turn out to be unimodal, or even log-concave. The aim of this talk is to present such an example. Recall that a sequence (fi)i=>0 of nonnegative integers is called unimodal if there exists an index h => 0 such that fi <= fi+1 for i < h and fi => fi+1 for i => h. The sequence is log-concave if fi2 => fi+1 fi-1 for i => 1, which implies the unimodality of (fi) if this sequence has no internal zeros.

An integer basis is a strictly increasing sequence B = (bi)i=>0 of positive integers with the following property: there exists a sequence (ci)i=>1 of positive integers (called multiplicity sequence) such that every positive integer n can be written uniquely in the form

n = a1b0 + a2b1 +... + akbk-1 with 0 <= ai <= ci and ak nonzero.

For instance, the most common integer bases are the powers of a fixed integer b => 2, (ie bi := bi); the associated multiplicity sequences are constant, given by ci = b-1 for all i => 1. Set θB(m,l) := # { n in {0,1,...,m-1}: n has l nonzero digits when written in basis B}. The result is: (θB(m,l))l=>0 is strongly log-concave, for any positive integer m and any integer basis B.

We will see that this result is indeed an inequality for elementary symmetric polynomials, and we will specialize it to obtain inequalities for sums of binomial coefficients, sums of Stirling numbers of the first kind, or sums of q-analogues of these numbers. I will end with a few words about a proof of this theorem.

Speaker's Contact Info: phpitt(at-sign)math.mit.edu

Return to seminar home page

Combinatorics Seminar, Mathematics Department, MIT, sara(at-sign)math.mit.edu

Page loaded on August 31, 2000 at 10:20 PM. Copyright © 1998-99, Sara C. Billey. All rights reserved.