An upper bound on the number of relevant variables in a bounded degree Boolean function on the Hamming graph

Alexandr Valyuzhenich

paper

An upper bound on the number of relevant variables in a bounded degree Boolean function on the Hamming graph

arXiv:2609.12540

Abstract

In this work, we prove that any Boolean function of degree $d$ on $Z_{q}^{n}$ , $q \geq 3$ , has at most $m_{q} q^{d}$ relevant variables, where $m_{q} = \frac{2 q ( q ^{2} + 4 q + 1 )}{( q - 1 ) ^{4}}$ . For $q \in {3, 4, 5, 6, 7}$ , we improve this bound to $2.854 \cdot 3^{d}$ , $1.749 \cdot 4^{d}$ , $1.263 \cdot 5^{d}$ , $0.994 \cdot 6^{d}$ , and $0.814 \cdot 7^{d}$ , respectively.