Inequalities and tail bounds for elementary symmetric polynomials

摘要

This paper studies the elementary symmetric polynomials Sk(x) for xRn. We show that if Sk(x)Sk+1(x) are small for some 0">k0 then S(x) is also small for all k">k. We use this to prove probability tail bounds for the symmetric polynomials when the inputs are only t-wise independent, that may be useful in the context of derandomization. We also provide examples of t-wise independent distributions for which our bounds are essentially tight.