On Fourier analysis of sparse Boolean functions over certain Abelian groups

Given an Abelian group G, a Boolean-valued function f: G -> -1, +1, is said to be s-sparse, if it has at most s-many non-zero Fourier coefficients over the domain G. In a seminal paper, Gopalan et al. proved "Granularity" for Fourier coefficients of Boolean valued functions over Z₂ⁿ, that have found many diverse applications in theoretical computer science and combinatorics. They also studied structural results for Boolean functions over Z₂ⁿ which are approximately Fourier-sparse. In this work, we obtain structural results for approximately Fourier-sparse Boolean valued functions over Abelian groups G of the form, G: = Z₏䃑^n₁. . . Z₏䂻^nₜ, for distinct primes pᵢ. We also obtain a lower bound of the form 1/ (m^2s) ᶜeiling (phi (m) /2), on the absolute value of the smallest non-zero Fourier coefficient of an s-sparse function, where m=p₁. . . pₜ, and phi (m) = (p₁-1). . . (pₜ-1). We carefully apply probabilistic techniques from Gopalan et al. , to obtain our structural results, and use some non-trivial results from algebraic number theory to get the lower bound. We construct a family of at most s-sparse Boolean functions over Zₚⁿ, where p > 2, for arbitrarily large enough s, where the minimum non-zero Fourier coefficient is 1/omega (n). The "Granularity" result of Gopalan et al. implies that the absolute values of non-zero Fourier coefficients of any s-sparse Boolean valued function over Z₂ⁿ are 1/O (s). So, our result shows that one cannot expect such a lower bound for general Abelian groups. Using our new structural results on the Fourier coefficients of sparse functions, we design an efficient testing algorithm for Fourier-sparse Boolean functions, thata requires poly ( (ms) ᵖhi (m), 1/epsilon) -many queries. Further, we prove an Omega (sqrts) lower bound on the query complexity of any adaptive sparsity testing algorithm.