An upper bound on the number of relevant variables for Boolean functions on the Hamming graph

The spectrum of a complex-valued function f on Zqⁿ is the set \|u|:u∈ Zqⁿ~and~f(u)≠ 0\, where $|u|$ is the Hamming weight of u and f is the Fourier transform of f. Let 1≤ d'≤ d≤ n. In this work, we study Boolean functions on Zqⁿ, q≥ 3, whose spectrum is a subset of \0\∪ ',…,d\. We prove that such functions have at most d/2· qd+d'2d'(q-1)d' relevant variables for d'+d≤ n+1. In particular, we prove that any Boolean function of degree d on Zqⁿ, q≥ 3, has at most dqᵈ⁺¹4(q-1) relevant variables. We also show that any equitable 2-partition of the Hamming graph $H(n,q)$, q≥ 3, associated with the eigenvalue $n(q-1)-qd$ has at most d/2· q²ᵈ2ᵈ(q-1)ᵈ relevant variables for d≤ n+1/2.