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 $$\text{bs}(f)\le \max \{s(f),C(f)-1\}\mathrm{.}$$ Consequently, only the three patterns $$s=\text{bs}=C,s=\text{bs}<C,s<\text{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})<\text{bs}({\sigma }_{n,d})<C({\sigma }_{n,d}),$$ and exhibit infinite families for which it holds.