Computing sparse Fourier sum of squares on finite abelian groups in quasi-linear time

The problem of verifying the nonnegativity of a function on a finite abelian group is a longstanding challenging problem. The basic representation theory of finite groups indicates that a function on a finite abelian group can be written as a linear combination of characters of irreducible representations of by ( ) = Sigma is an element of ( ) ( ) , where is the dual group of consisting of all characters of and ( ) is the Fourier coefficient of at is an element of . 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 on a finite abelian group with complexity that is quasi-linear in the order of and polynomial in the FSOS sparsity of . Moreover, for a nonnegative function on a finite abelian group and a subset subset of , we give a lower bound of the constant such that + admits an FSOS supported on . 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 by sparse FSOS.