An approach to the moments subset sum problem through systems of diagonal equations over finite fields

Abstract

Let ${\mathbb{F}}_q$ be the finite field of $q$ elements, for a given subset $D\subset {\mathbb{F}}_q$, $m\in \mathbb{N}$, an integer $k\le |D|$ and $\mathbf{b}\in {\mathbb{F}}_q^m$ we are interested in determining the existence of a subset $S\subset D$ of cardinality $k$ such that ${\sum }_{a\in S}{a}^i=b_i$ for $i=1,\dots ,m$. This problem is known as the moment subset sum problem and it is $NP$-complete for a general $D$. We make a novel approach of this problem trough algebraic geometry tools analyzing the underlying variety and employing combinatorial techniques to estimate the number of ${\mathbb{F}}_q$-rational points on certain varieties. We managed to give estimates on the number of ${\mathbb{F}}_q$-rational points on certain diagonal equations and use this results to give estimations and existence results for the subset sum problem.

25 pages