On Fourier analysis of sparse Boolean functions over certain Abelian groups

Given an Abelian group G, a Boolean-valued function $f: G \to \{-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. in ``Testing Fourier dimensionality and sparsity'' proved ``Granularity'' for Fourier coefficients of Boolean valued functions over $\mathbb{Z}_2^n$, that have found many diverse applications in theoretical computer science and combinatorics. They also studied structural results for Boolean functions over $\mathbb{Z}_2^n$ 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:= \mathbb{Z}_{p_1}^{n_1} \times \cdots \times \mathbb{Z}_{p_t}^{n_t}$, for distinct primes p_i. We also obtain a lower bound of the form $1/(m^{2}s)^{\lceil \varphi(m)/2 \rceil}$, on the absolute value of the smallest non-zero Fourier coefficient of an s-sparse function, where $m=p_1 \cdots p_t$, and $\varphi(m)=(p_1-1) \cdots (p_t-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.