Certificate Complexity of Elementary Symmetric Boolean Functions of Arbitrary Degree
Abstract
Let σn,d denote the elementary symmetric Boolean function of n variables and degree d. Previous work determined C(σ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≤ d≤ n, thereby completing the classification for elementary symmetric Boolean functions. Writing d=2t m with m odd, we obtain an explicit formula in which the possible deficit from the maximal value n is controlled by 2t, while the exact value is determined by a binary containment condition involving m. In particular, n−2ν2(d)+1≤ C(σn,d)≤ n, and we characterize when the upper bound is attained. Moreover, we determine the least positive period of the certificate-complexity deficit Δd(n)=n−C(σn,d): it is $1$ for odd d, equals d when d is a power of two, and equals 2⌊log2 d⌋+1 for even non-power-of-two d. This least-period problem is distinct from the classical periodicity of the underlying value sequence binomjdbmod 2. The known odd-degree and power-of-two formulas are recovered as special cases.
Related
- Sensitivity and Block Sensitivity of Elementary Symmetric Boolean Functions of Arbitrary Degree
- Block Sensitivity and Certificate Complexity of Rotation Symmetric Boolean Functions
- Fractional elementary symmetric functions and Hessian estimates in the plane
- Elementary modal logics and circuit complexity
- On the Injectivity of Elementary Symmetric Partitions and the Multiset Recovery Problem
BibTeX
@misc{zhang2026certificate,
title = {{Certificate Complexity of Elementary Symmetric Boolean Functions of Arbitrary Degree}},
author = {Jing Zhang and Yuan Li},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.15678},
eprint = {2609.15678},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.15678},
note = {CC0},
}
RIS
TY - UNPB
TI - Certificate Complexity of Elementary Symmetric Boolean Functions of Arbitrary Degree
AU - Jing Zhang
AU - Yuan Li
PY - 2026
DA - 2026/09/26
PB - arXiv
DO - 10.48550/arxiv.2609.15678
UR - https://arxiv.org/abs/2609.15678
AB - Let σ_n,d denote the elementary symmetric Boolean function of n variables and degree d. Previous work determined C(σ_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≤ d≤ 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≤ C(σ_n,d)≤ n, and we characterize when the upper bound is attained. Moreover, we determine the least positive period of the certificate-complexity deficit Δ_d(n)=n−C(σ_n,d): it is $1$ for odd d, equals d when d is a power of two, and equals 2^⌊log_2 d⌋+1 for even non-power-of-two d. This least-period problem is distinct from the classical periodicity of the underlying value sequence binomjdbmod 2. The known odd-degree and power-of-two formulas are recovered as special cases.
ER -