Sensitivity and Block Sensitivity of Elementary Symmetric Boolean Functions of Arbitrary Degree

Let ${\sigma }_{n,d}$ denote the elementary symmetric Boolean function of $n$ variables and degree $d$. We completely determine the sensitivity, average sensitivity, and block sensitivity of ${\sigma }_{n,d}$ for every $1\le d\le n$. Using Lucas' theorem, we obtain a uniform binary description of the Hamming-weight value sequence, from which the sensitivity and average-sensitivity formulas follow and the computation of block sensitivity reduces to at most four explicit candidates. Combining these results with the arbitrary-degree formula for certificate complexity, we determine the exact relations among sensitivity, block sensitivity, and certificate complexity. We also prove a general result for symmetric Boolean functions: every nonconstant symmetric Boolean function $f$ satisfies \[ \bs(f)\le \max\{s(f),C(f)-1\}. \] Consequently, only the three patterns \[ s=\bs=C,\qquad s=\bs<C,\qquad s<\bs<C \] can occur for nonconstant symmetric Boolean functions. For elementary symmetric Boolean functions, we give necessary and sufficient conditions for each of these three patterns, thereby completely classifying the relations among $s({\sigma }_{n,d})$, $\text{bs}({\sigma }_{n,d})$, and $C({\sigma }_{n,d})$. In particular, we obtain a necessary and sufficient characterization of the full strict hierarchy \[ s(\sigma_{n,d})<\bs(\sigma_{n,d})<C(\sigma_{n,d}), \] and exhibit infinite families for which it holds.