{"id":"arxiv/2609.15678","url":"https://arxiv.org/abs/2609.15678","tags":["math.CO","cs.DM"],"score":0,"title":"Certificate Complexity of Elementary Symmetric Boolean Functions of Arbitrary Degree","domain":"math.CO","source":"arxiv","authors":["Jing Zhang","Yuan Li"],"reviews":0,"subject":"math.CO","summary":"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\\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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-14","reactions":{}}