  The problem of verifying the nonnegativity of a function on a finite abelian
group is a long-standing challenging problem. The basic theory of
representation theory of finite groups indicates that a function $f$ on a
finite abelian group $G$ can be written as a linear combination of characters
of irreducible representations of $G$ by $ f(x)=\sum_{\chi \in \widehat{G}}
\widehat{f} (\chi)\chi(x)$, where $\widehat{G}$ is the dual group of $G$
consisting of all characters of $G$ and $ \widehat{f} (\chi)$ is the Fourier
coefficient of $f$ at $\chi \in \widehat{G}$. In this paper, we show that by
performing the fast (inverse) Fourier transform, we are able to compute a
sparse Fourier sum of squares (FSOS) certificate of $f$ on a finite abelian
group $G$ with complexity \if $\operatorname{O}\left(|G|
\log(|G|)+\log(k_{\min})\operatorname{SDP}(2k_{\min})\right)$,\fi that is
quasi-linear in the order of $G$ and polynomial in the FSOS sparsity \if
$k_{\min}$\fi of $f$. Moreover, for a nonnegatvie function $f$ on a finite
abelian group $G$ and a set $S \subset \widehat{G}$, we give a lower bound of
the constant $M$ such that $f+M$ admits an FSOS supported on} $S$. We
demonstrate the efficiency of the proposed algorithm by numerical experiments
on various abelian groups of orders up to $10^7$. As applications, we also
solve some combinatorial optimization problems and the sum of Hermitian squares
(SOHS) problem \if on $\mathbb{T}^n$\fi by sparse FSOS.
