2024/04/16 by Alexandr Valyuzhenich, Valyuzhenich, Alexandr
Computer Science · Mathematics · #Analytic Number Theory Research #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2404.10418
openalex publication_date 2024/04/16 · openalex created_date 2024/04/18 · openalex updated_date 2026/07/28
The spectrum of a complex-valued function f on ℤqn is the set \|u|:u∈ ℤqn~and~\widehatf(u)≠ 0\, where |u| is the Hamming weight of u and \widehatf is the Fourier transform of f. Let 1≤ d'≤ d≤ n. In this work, we study Boolean functions on ℤqn, q≥ 3, whose spectrum is a subset of \0\∪ \d',…,d\. We prove that such functions have at most (d)/(2)⋅ \fracqd+d'2d'(q-1)d' relevant variables for d'+d≤ n+1. In particular, we prove that any Boolean function of degree d on ℤqn, q≥ 3, has at most \fracdqd+14(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)⋅ \fracq2d2d(q-1)d relevant variables for d≤ (n+1)/(2).