Certificate Complexity of Elementary Symmetric Boolean Functions of Arbitrary Degree

Abstract

Let ${\sigma }_{n,d}$ denote the elementary symmetric Boolean function of $n$ variables and degree $d$. Previous work determined $C({\sigma }_{n,d})$ when $d$ is odd or a power of two, but the general even non-power-of-two case remained open. We determine the certificate complexity for every degree $1\le d\le n$, thereby completing the classification for elementary symmetric Boolean functions. Writing $d=2^{t}m$ with $m$ odd, we obtain an explicit formula in which the possible deficit from the maximal value $n$ is controlled by $2^t$, while the exact value is determined by a binary containment condition involving $m$. In particular, \[ n-2^{ν_2(d)}+1\le C(σ_{n,d})\le n, \] and we characterize when the upper bound is attained. Moreover, we determine the least positive period of the certificate-complexity deficit ${\Delta }_d(n)=n-C({\sigma }_{n,d})$: it is $1$ for odd $d$, equals $d$ when $d$ is a power of two, and equals $2^{\lfloor {\log }_{2}d\rfloor +1}$ for even non-power-of-two $d$. This least-period problem is distinct from the classical periodicity of the underlying value sequence $\left(\genfrac{}{}{0ex}{}{j}{d}\right)\mathrm{mod}2$. The known odd-degree and power-of-two formulas are recovered as special cases.